ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural Championship 2004 Round 1

About     Problems     Submit solution     Judge status     Standings
Contest is over

C. Dispute

Time limit: 0.5 second
Memory limit: 64 MB
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)x5 + x3 – xy + 3x + 7y) % 9973, the symbol % denotes taking the residue of division.

Input

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

Output

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

Sample

inputoutput
50
6300
Problem Author: Idea - Alexander Klepinin, prepared by Alexander Klepinin, Stanislav Vasilyev
Problem Source: VIII Collegiate Students Urals Programming Contest. Yekaterinburg, March 11-16, 2004
To submit the solution for this problem go to the Problem set: 1309. Dispute