TopCoder

Thumb rezero
Re Zero
Re Zero

User's AC Ratio

62.5% (5/8)

Submission's AC Ratio

24.1% (7/29)

Description

還記得小向嗎?對,就是那個天龍國的天才魔法少女。
身為天龍國的魔法少女,每天吃早餐是一定要的,小向每天都會在去上學的路上買早餐來吃。(雖然小向是天才魔法少女,但是她還是喜歡去學校轉眼皮)
有天,小向又想要吃早餐了,她決定去買魔法早餐來吃。

這時候問題就來了,
我們都知道,所謂的魔法早餐店,一定是開在一排房子前面,這樣路過的小向跟眼皮醬們才可以買魔法早餐補充魔力。
因為小向住的地方是魔法空間裡的一排房子,所以小向決定到開在這些房子前面的魔法早餐店買魔法早餐。
魔法早餐店有一個特性,我們可以找到N個兩兩互質的整數$A_ 1 ~ A_ n$,
而魔法空間的房子編號就是$0~ \prod_ {k=1}^ n A_ k$($A_ 1 ~ A_ n$的乘積)。
這些魔法空間的房子,要是它的編號可以被任何一個整數$A_ i$整除(餘數為0)的話,那這間房子前面就會有一家魔法早餐店。

小向想要算出每間房子和他最近的魔法早餐店的距離和,雖然不知道為什麼她想知道,但是要是不知道的話小向就會一整個學期失眠。
剛好你,天龍國資深房地產經紀人,想要投資魔法空間的房地產,你發現魔法早餐店跟魔法空間裡的房子的距離會直接影響到房價,
於是你決定幫助小向,算出所有的房子到它最近的魔法早餐店的距離和是多少。

由於答案可能是個很大很大的魔法數字,為了讓凡人可以看得懂,你只要算出答案$mod (10^ 9 + 7)$的值就可以了。

Input Format

第一行有一個整數t,代表總共有t筆測資。
對於每筆測資,
第一行有一個整數n,
第二行有n個兩兩互質的整數$A_ 1 ~ A_ n$。

對於30%的測資,$1 \leq n \leq 5$,$\prod_ {k=1}^ n A_ k \leq 10^ 5$
對於100%的測資,
$1 \leq t \leq 10$
$1 \leq n \leq 1000$
最小的$A_ i \leq 10^ 4$,最大的$A_ i \leq 2^ {31} -1$

Output Format

對於每一筆測試資料輸出一行,
每行一個整數,代表所有魔法空間的房子到他們最近的魔法早餐店的距離和($mod (10^ 9 + 7)$)。

Sample Input

3
2
2 3
3
4 3 7
4
4 5 3 7

Sample Output

2
36
144

Hints

對於第一筆測試資料,總共有7間房子(編號0到6),其中0、2、3、4、6號房子前面有魔法早餐店,所以距離和為2。

Problem Source

2015建中校隊入隊考試-複試
題目改編自IMO Shortlist 2014N6:
http://www.artofproblemsolving.com/community/c6h1113200p5083572

Subtasks

For Testdata: 0 ~ 0, Score: 30
For Testdata: 1 ~ 2, Score: 70
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 5000 65536 65536
1 5000 65536 65536
2 5000 65536 65536