URAL/1309

来自"NOCOW"

#include <iostream>
#define sqr(x) ((x)*(x))
using namespace std;
const int P=9973;
int N,ans=0,a[P+1]={0},b[P+1]={0},u[P+1],v[P+1];
int main()
{
    cin >> N;
    for (int i=1;i<=P;i++)
    {
        int t1=sqr(i)%P;
        int t2=((sqr(t1)%P)*i)%P;
        u[i]=(t2+7-i+P)%P;
        v[i]=((t1*i)%P-t2+3*i+P)%P;
    }
    a[0]=1;
    for (int i=1;i<=P;i++)
    {
        a[i]=(a[i-1]*u[i])%P;
        b[i]=(b[i-1]*u[i]+v[i])%P;
    }
    for (int i=N/P;i>0;--i)
        ans=(ans*a[P]+b[P])%P;
    ans=(ans*a[N%P]+b[N%P])%P;
    cout << ans << endl;
    return 0;
}
//by zzy