Problem Description

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.

Input

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).

Output

For each case, print A(N+1) mod 112233 in a single line.

1
18605
5
19543
19998
12266
27854
2103

18605
110887