NREcou

#include<fstream>
#define MOD 1000000017
using namespace std;
ifstream  fin("nrecou.in");
ofstream fout("nrecou.out");
long long n;
long long Power(long long b)
{
    long long p=1, x=10;
    while(b)
    {
        if(b%2)
            p=(p*x)%MOD;
        x=(x*x)%MOD;
        b=b/2;
    }
    return (p*9)%MOD;
}
long long Solutie(long long n)
{
    long long p, v1[20000], v2[20000], s=0;
    int i, j, nv1, nv2;
    nv1=1;
    v1[1]=1;
    nv2=0;
    for(p=2;p*p<=n;p++)
        if(n%p==0)
        {
            nv1++;
            v1[nv1]=p;
            nv2++;
            v2[nv2]=n/p;
        }
    if(v1[nv1]==v2[nv2])
        nv2--;
    for(i=nv2;i>=1;i--)
    {
        nv1++;
        v1[nv1]=v2[i];
    }
    v2[1]=9;
    s=v2[1];
    for(i=2;i<=nv1;i++)
    {
        v2[i]=Power(v1[i]-1);
        for(j=1;j<=i-1;j++)
            if(v1[i]%v1[j]==0)
                v2[i]=(v2[i]+MOD-v2[j])%MOD;
        s+=v2[i];
        s%=MOD;
    }
    return s;
}
int main()
{
    fin>>n;
    fout<<Solutie(n);
    return 0;
}