TopCoder

skylinebaby
激しい「喜び」はいらない… そのかわり深い「絶望」もない……… 「植物の心」のような人生を… そんな「平穏な生活」こそ私の目標だったのに………

User's AC Ratio

54.5% (6/11)

Submission's AC Ratio

25.7% (9/35)

Tags

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 1

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

Sample Output 1

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

No. Testdata Range Score
1 0 30
2 1~2 70

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 5000 65536 262144 1
1 5000 65536 262144 2
2 5000 65536 262144 2