NPSC 魔法學院在今年正式成立囉！

從小就展現過人天賦的天才兒童殿壬，如今已成長茁壯並成為NPSC 魔法學院第一屆的學員了。一年級的課程對於殿壬來講根本就是小菜一碟，所以他跟著學院裡的教授一起衝鋒陷陣，研究最新穎的魔法技術：魔法鏈。

施展這種法術前，殿壬要先擁有一串由魔法寶石組成的魔力串珠。一串魔力串珠會由$N$ 顆魔法寶石組成，每顆魔法寶石都是相異的，用數字$1$ 到$N$ 表示。一串魔力串珠中還會有$N - 1$條線，每條線連接兩顆相異的魔法寶石，使得這$N$ 顆魔法寶石都會被串在一起（任兩顆魔法寶石都會透過一或多條線的串接而連接著）。

這項法術的施展，就是利用這串魔力串珠來製造一條魔法鏈。

製造魔法鏈時，若這串魔力串珠只有2 顆魔法寶石，就直接用魔力剪刀剪斷中間唯一的那條線，並且把這2 顆魔法寶石依任意順序放在魔法鏈的第1 跟第2 個位置。

否則，殿壬要挑選魔力串珠中的一條線並用魔力剪刀把它剪斷，使得在剪斷之後會形成一串有多顆魔法寶石的魔力串珠以及一顆獨立的魔法寶石（如果剪斷後不會變成這種結果，那麼殿壬就不能剪這條線），接著把這獨立的魔法寶石放在魔法鏈的下一個位置（剪第一刀時得到的魔法寶石放在第一個位置、剪第二刀時得到的魔法寶石放在第二個位置，依此類推），重複上述動作直到這串魔力串珠只剩下兩顆魔法寶石（中間由一條線連接著）時，殿壬就把最後這條線剪斷，並依他的選擇將最後的兩顆魔法寶石放在魔法鏈的第$N - 1$ 跟第$N$ 個位置。不難發現，就算是同樣的魔力串珠，也可以藉由不同的剪取順序而排出許多不同的魔法鏈，以下圖的魔力串珠（與範例一相同）為例，$2, 3, 5, 1, 4$、$5, 2, 4, 1, 3$ 跟$5, 2, 4, 3, 1$ 都是可能創造出的魔法鏈，不過$2, 1, 3, 4, 5$ 跟$2, 3, 4, 5, 1$ 就是不可能創造出來的魔法鏈。

​

現在給你一串魔法串珠，請你計算總共可以創造出多少種不同的魔法鏈。兩個魔法鏈只要任一個對應的位置不相等，就視為不同。因為答案可能很大，你的程式只需要輸出答案除以$10^ 9 + 7$的餘數即可。