ENG  RUS Timus Online Judge Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

## 1309. 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
Tags: none