PE511

import java.util.*;

public class P511
{
    static final int mod = 1_000_000_000;
    static final int k = 4321, kpow = 8192;
    static final int[] cnt = new int[k];
    static final int[][] dp = new int[128][];

    static int[] rek(final long n, final int log)
    {
        if(dp[log]!=null) return dp[log];
        if(n==1) return dp[log] = cnt;

        final int[] a = n%2!=0 ? cnt : rek(n/2,log+1),
        b = n%2!=0 ? rek(n-1,log+1) : rek(n/2,log+1);

        final int[] v = new int[2*kpow], u = new int[2*kpow];
        System.arraycopy(a,0,v,0,k);
        System.arraycopy(b,0,u,0,k); System.arraycopy(b,0,u,k,k);
        final int[] w = karatsuba(v, u, 0, 2*kpow);

        return dp[log] = Arrays.copyOfRange(w, k, 2*k);
    }
    static int[] karatsuba(final int[] v, final int[] u, final int off, final int len)
    {
        if(len<=32)
        {
            final int[] w = new int[2*len-1];
            for(int i = 0; i<len; i++)
            {
                final long mul = v[off+i];
                if(mul!=0)
                    for(int j = 0; j<len; j++)
                        w[i+j] = (int)((w[i+j] + mul*u[off+j])%mod);
            }
            return w;
        }

        final int[] w1 = karatsuba(v, u, off+len/2, len/2), w2 = karatsuba(v, u, off, len/2);
        final int[] v2 = new int[len/2], u2 = new int[len/2];
        for(int i = 0; i<len/2; i++) v2[i] = (v[off+i] + v[off+i+len/2])%mod;
        for(int i = 0; i<len/2; i++) u2[i] = (u[off+i] + u[off+i+len/2])%mod;
        final int[] w3 = karatsuba(v2, u2, 0, len/2), w = new int[2*len-1];

        System.arraycopy(w2,0,w,0,len-1);
        System.arraycopy(w1,0,w,len,len-1);
        for(int i = 0; i<len-1; i++)
            w[i+len/2] = (int)(((long)w[i+len/2]+w3[i]-w2[i]-w1[i]+2*mod)%mod);
        return w;
    }

    public static void main(String[] klein)
    {
        final long n = 1234567898765L;
        for(long div = 1; div*div<=n; div++)
            if(n%div==0)
            {
                cnt[(int)(div%k)]++;
                if(div*div!=n) cnt[(int)(n/div%k)]++;
            }
        System.out.println("Svar: " + rek(n,0)[(int)((k-n%k)%k)]);
    }
}