记下标从 1 开始。有长为 n 的整数数组 a ，下标为 i 的元素为 a_i 。
设整数自变量 1\le x\le n ，设常数 r=1437580，有函数 f(x)： f(x)=\sum_{i=1}^xr^i\cdot a_i
设 p = (114514 * (54 - 1 + 114 * (1 + 14 * 5 + 1 + 4))) + (4 + 11451 * (4 - 1 - 15 + 14)) + (11 + 41 * 54 + (141 + 541)) + (4 - 1 - 15 + 14) 。
请你求函数值对 p 取模后的结果。
输入
输入第一行一个整数 n(1\le n\le10^5)
接下来输入一行 n 个整数，第 i 个整数为 a_i(0\le a_i\le10^9)
接下来输入一行一个整数 t(1\le t\le10^5) ，代表有 t 次询问
接下来输入一行 t 个整数，第 i 个整数为 x_i(1\le x_i\le n)
输出
对于每个 x_i ，输出一行一个整数代表 f(x_i)\bmod p
样例
| 标准输入 复制文本 |
3 1 0 2 3 1 3 2 |
| 标准输出 复制文本 |
1437580 178683454 1437580 |
提示
update: 21/11/22 原数据有误，已修复并增强了数据