ShadowIterator在学校这么吊，被家长知道了！于是，家长们联合起来准备给ShadowIterator致命一击。
一个有N个家长对ShadowIterator发动攻击，第i个家长的攻击力x_i是一个范围在1到m_i之间的整数。
每个家长学的武功都不是同一门派的，比如说华山派、武当派、少林派、崆硐派、古墓派、苹果派、π派……所以真正有效的攻击力是可能是很小的（当然也可能很大）——等于gcd(x₁,x₂,...,x_N)。
由于这些家长缺乏合作的理念，完全不懂得配合，所以他们总是在自己的攻击力范围中随机选一个值作为这次进攻的攻击力x_i。
ShadowIterator早已被一群家长吓傻了，但是大敌当前怎能束手就擒呢？ShadowIterator想知道这N个家长的有效攻击力的所有可能（共有m₁*m₂*...*m_N种可能值）的总和是多少。由于这个数可能比较大，输出它mod 10007的值。

第一行一个整数N
第二行N个整数m_i，表示第i个家长的攻击力范围。

一个整数，所有可能的总和mod 10007的值。

样例解释：
两个家长的攻击力可能为(1,1),(1,2),(2,1),(2,2)，有效攻击力分别为1,1,1,2，所以有效攻击力总和为5.

数据范围：
对于5%的数据，N=1
对于另外5%的数据，N=2
对于30%的数据，m₁*m₂*...*m_N<=5*10⁶
对于100%的数据，1<=N<=1000，1<=m_i<=10⁶