给定 K 次多项式 f (x) = a0 + a1x + a2x^2 + · · · + aKx^K。
把所有不超过 n 次的单位根列在一起,设为 r1, r2, · · · , rm。
将这些根去重后,写在一起,设为 r′1, r′2, · · · , r′k,需要求表达式 ∑f (r′i) 的值。
输入格式
第一行包含两个非负整数 n, K,表示单位根的最高次数和多项式的次数。
第二行包含 K + 1 个整数 a0, a1, · · · , aK,依次表示这些多项式的系数。
输出格式
输出一行一个整数,表示表达式的值。可以证明,答案一定是一个整数,且在给定数据规模下,答案在带符号 128 位整数范围内。
样例 1 输入
4 1
-1 2
样例 1 输出
-8
样例 2 输出
6 7
2 0 0 3 0 7 3 1
样例 2 输出
57
样例 3
见下发文件
数据范围
对于所有的测试点,均满足 1 ≤ n ≤ 2^31 − 1; 0 ≤ K ≤ 10^7; −9999 ≤ ai ≤ 9999。