Dispute is a great thing! It is known that the truth is born in a dispute. Two organizers of the Ural Championship have an argument. The first of them says that computing the value of a function is a very stupid and useless problem for a programming contest. His reasoning is that when the definition of a function is known and there is enough time for the necessary preparations, it is possible to calculate the value of the function at any point very fast. The second organizer asserts that not any function can be calculated fast enough. To resolve this dispute, they decided to make an experiment. So you are to prove that you are really able to calculate the value of a function at any point fast enough.

The function f(n), where n is an integer, is defined recursively by the following expressions:

• f(0) = 0,
• f(n) = g(n, f(n-1)),

where g(x,y) = ((y-1)x⁵ + x³ – xy + 3x + 7y) % 9973, the symbol % denotes taking the residue of division.

The only line contains an integer n (0 ≤ n ≤ 10⁸).

You are to write a program that outputs the value f(n). And it should perform the necessary computations very fast!