Generally speaking, the last problem of a warm-up contest should be the most difficult one.

Let $M = 10^9 + 7$. We are given a sequence $A$ such that for $i \ge 1$, $A_i = ((A_{i-1} \times 1234567 + 7654321) \pmod M) \oplus 998244353$, where $\oplus$ represents the bitwise XOR operation.

As for $A_0$, there are several problem setters for this contest. The possible values of $A_0$ are the birthdays of all the problem setters, presented in the format of the first two digits for the month and the last two digits for the day. For example, if a problem setter's birthday is August 13th, then $A_0 = 813$ is a possible value; or if a problem setter's birthday is November 6th, then $A_0 = 1106$ is a possible value.

Now, we want you to output any one possible value of $A_{100000000}$ (where the subscript is $10^8$).

Input

There is no input for this problem.

Output

Output any one possible value of $A_{100000000}$.

Note

When $A_0 = 0$, $A_{100000000} = 322929978$. You can use this data to test the correctness of your program.