OI题库

【题目描述】

辩论是件好事！众所周知，真理越辩越明。Ural锦标赛的两名组织者进行了一场辩论。第一个人说，对于编程竞赛而言，计算一个函数的值是一道非常愚蠢而且无用的题目。他的论证是：一旦一个函数的定义已知，并且有充分时间做必要的准备，就可以很快计算出这个函数在任意一点的值。第二名组织者却认为并非所有的函数都可以被足够快地计算出来。为了结束这场辩论，他们决定做一个试验。因此你需要证明你的确可以足够快地计算一个函数在任意一点的值。

这个函数f(n)，其中n是非负整数，递归定义如下：

f(0)=0

f(n)=g(n,f(n-1))，

其中g(x,y)=( (y-1)x^5 +x^3 - xy + 3x + 7y) % 9973，这里%符号代表取模（即C/C++中的%）

【输入格式】

输入文件有一行一个整数n（0<=n<=10^8）.

【输出格式】

输出一行一个整数f(n)。

【样例输入】

50

【样例输出】

6300

【提示】

你得写一个程序输出f(n)的值。并且它必须运行的非常快！

【来源】

Ural 1309 Dispute

Problem Author: Idea - Alexander Klepinin, prepared by Alexander Klepinin, Stanislav Vasilyev
Problem Source: VIII Collegiate Students Urals Programming Contest. Yekaterinburg, March 11-16, 2004