和和和和和

给n个数A1,A2....An,你可以选择一个区间(也可以不选)，区间里每个数x变成f(x),其中f(x)=(1890x+143)mod10007。问最后n个数之和最大可能为多少。

输入有多组数据。
每组数据第一行包含一个整数n.(1≤n≤10⁵)
第二行n个整数A1,A2....An.(0≤Ai≤10⁴)
数据保证∑n ≤10⁶

对于每组数据输出一行答案.

2
10000 9999
5
1 9999 1 9999 1

19999
22033