给定整数 n,a,b,c，令 M = 11111111；

有数列 f_i = (a \times i^2 + b \times i + c) \mod M （1 \le i \le n）。

将数列 f_i 排序、去重后得到新的数列 g_i，设数列 g_i 有 m 个数，则通过计算 g_i 中每一项的数值和项数的乘积和 (\sum g_i \times i) \mod M (1 \le i \le m) 即是本题的计算结果。

请根据题意计算出整数计算的结果。

输入四个整数 n,a,b,c ；

输出按题意计算的结果。

样例 1 解释

f_i 数列有 3 个整数，分别是 2、2、2，排序去重后得到的数列 g_i 仅有 1 个整数 2，按题意计算出的结果 =(2\times1) \mod M=2 。

样例 2 解释

f_i 数列有 5 个整数，分别是 6、11、18、27、38，排序去重后结果不变，按题意计算出的结果 =(6 \times 1+11 \times 2+18 \times 3+27 \times 4+38 \times 5) \mod M=380。

数据范围

对于 30\% 的数据， n ≤ 10^3 。

对于 60\% 的数据， n ≤ 10^5 。

对于 100\% 的数据， 1 ≤ n ≤ 10^7， 0 ≤ a, b, c ≤ 100。

友情提醒

请特别注意本题的数据范围。

东方博宜OJ

月赛