Let A(x) = Sigma(Ai * x^i) (0<=i<=N-1). Given A(1), A(2),..., A(N), You are asked to calculate A(N+1) mod 112233. It is guaranteed that A(1), A(2), …, A(N), A(N+1) are all integers.
输入解释
There are multiple test cases, ended with an EOF. For each case: Line 1 contains a positive integer N (N <= 10^6). Line 2 to Line N+1: each contains a non-negative integer less than 65536. The integer in Line i is A(i-1).
输出解释
For each case, print A(N+1) mod 112233 in a single line.