给n个数${A}_{1},{A}_{2}....{A}_{n}$,你可以选择一个区间(也可以不选)，区间里每个数x变成f(x),其中$f(x)=(1890x+143) mod 10007$。问最后n个数之和最大可能为多少。
输入有多组数据。
每组数据第一行包含一个整数n.$(1\leq n\leq {10}^{5})$
第二行n个整数${A}_{1},{A}_{2}....{A}_{n}$.$(0\leq {A}_{i}\leq {10}^{4})$
数据保证 $\sum n\leq {10}^{6}$.
对于每组数据输出一行答案.
2 10000 9999 5 1 9999 1 9999 1
19999 22033