PE546

#include <iostream>
#include <cstdio>

typedef long long big;
#include "10.txt"

#define M 49
#define N 50
#define K 10
#define INPUT 100000000000000LL
#define PRE 1000000
#define MOD 1000000007

big (*precomputed)[N];

int main(int argc, char **argv) {

    precomputed = (big (*)[N])malloc(sizeof(big) * PRE * N);

    /* LOOP TO PRECOMPUTE VALUES */
    //-- i: value of n that we will be computing
    //-- j: index of function that we will be computing
    // precompute values for all functions up until PRE
    for (int i=0;i<PRE;i++) {
        for (int j=0;j<N;j++) {
            // initialize all funcs f(0) = 1
            if (!i) {
                precomputed[i][j] = 1;
            } else {
                // if this is the actual f(n)
                if (!j) {
                    // the formula from the problem
                    precomputed[i][j] = (precomputed[i-1][j] + precomputed[i/K][j]) % MOD;
                } else {
                    precomputed[i][j] = (precomputed[i-1][j] + precomputed[i][j-1]) % MOD;
                }
            }
        }
    }


    /* ACTUALLY CALCULATE F(INPUT) */

    //-- this is the value that we are currently at. The expression is in terms of functions of this value
    //-- once it goes down below PRE, we can evaluate
    big current = INPUT;

    //-- this is the vector of coefficients of each function for the current value. So, at all times,
    //-- f(INPUT) = multiply[0]*f(current) + multiply[1]*g(current), + ....
    big multiply[N];

    multiply[0] = 1;
    for (int i=1;i<N;i++) multiply[i] = 0;

    while (current >= PRE) {
        // find the modulus
        int mod = current % K;

        //-- this is the array of values in the form temp[M][j] * M(K*k+j). we are done when all entries are zero
        big temp[M][K];
        memset(temp,0,sizeof(temp));

        // move all values of "multiply" into this array as appropriate
        for (int i=0;i<M;i++) {
            temp[i][mod] = multiply[i];
        }

        // clear out the "multiply" array, it will be repopulated
        memset(multiply,0,sizeof(multiply));

        bool morechange = true;
        //-- we will bail out as soon as the "temp" array is all 0s
        while (morechange) {

            morechange = false;

            // iterate thorugh all functions
            for (int i=0;i<M;i++) {

                // iterate through all remainders
                for (int j=0;j<K;j++) {

                    if (!temp[i][j]) continue; // there is nothing to do here
                    morechange = true;

                    // if we are in function 0, we simply add the value to the output j times

                    if (!i) {
                        multiply[0] = (multiply[0] + ((j * temp[i][j]) % MOD)) % MOD;

                    } else { // otherwise, we need to increment the value for the previous function
                        for (int rem=1;rem<=j;rem++) {
                            temp[i-1][rem] = (temp[i-1][rem] + temp[i][j]) % MOD;
                        }
                    }


                    // and of course, use the coefficients table to map out lower-order coefficients
                    for (int func=0;func<N;func++) multiply[func] = (multiply[func] + (coefficient[i][func] * temp[i][j] % MOD)) % MOD;

                    // this entry was used up fully
                    temp[i][j] = 0;

                }
            }

        }

        current /= K;
    }

    //-- now obtain the final sum using the lookup table
    big answer = 0;
    for (int i=0;i<N;i++) {
        answer = (answer + (multiply[i] * precomputed[current][i] % MOD)) % MOD;
    }

    std::cout << answer;
}