寻找阵营

Time Limit: 1500ms

Memory Limit: 65536KB

Description

  在新世界中,每个人一出生就携带着一串序列号,这串序列号由一个数组组成。这个数组除了有标志不同人的作用之外,还有一个作用就是用来规定派别,一个派别有一个吉祥数字n。一个派别的所有的人的序列号均满足以下条件,数组长度k(1 < k <= 100000)均相同,序列号元素di(1 <= di <= n),gcd(d1,…,dk,n) = 1。   约翰也有着这样一串序列号,他想稍微修改一下这串序列号,将相邻两个数字相加合成一个数(最多修改一次,或不修改,修改太多容易被发现),他想知道,如何才能让自己派别能容纳的人最多,约翰的派别中吉祥数字n若有多个满足条件,则取最小值;所有的d均小于100000,请输出该派别的最大容纳人数(包括他自己)。

Input

  每组测试样例中只有一组数据,数据有两行,第一行为约翰本身的数组长度,第二行为约翰的序列号。

Output

  输出一行数据,表示约翰所属的阵营中最大容纳人数。数字有可能很大,所以输出方案数mod 1e9 + 7

Sample Input

3
1 2 3

Sample Output

26

Hint

None

Source

None

提交代码