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

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

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

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