Arithmetic Equality

#include <iostream>

using namespace std;

const int MOD = 1e9 + 7;
const int NMAX = 1e5;

int digits, sol;

int fact[NMAX + 5], invFact[NMAX + 5];

int LgPut(int base, int exp)
{
    int ans = 1, aux = base;

    for(int i = 1; i <= exp; i <<= 1)
    {
        if(i & exp)
            ans = (1LL * ans * aux) % MOD;

        aux = (1LL * aux * aux) % MOD;
    }

    return ans;
}

void PrecFact()
{
    fact[0] = 1;
    for(int i = 1; i <= digits; i++)
        fact[i] = (1LL * i * fact[i - 1]) % MOD;

    invFact[0] = 1;
    for(int i = 1; i <= digits; i++)
        invFact[i] = LgPut(fact[i], MOD - 2);
}

int Comb(int n, int k)
{
    int res = fact[n];
    res = (1LL * res * LgPut(fact[k], MOD - 2)) % MOD;
    res = (1LL * res * LgPut(fact[n - k], MOD - 2)) % MOD;
    return res;
}

int st[11];
void CheckSol(int prod, int sum, int digitsLeft)
{
    if(prod == sum + digitsLeft)
    {
        int currSol = 1, d = digits;

        for(int i = 2; i <= 9; i++)
        {
            currSol = (1LL * currSol * Comb(d, st[i])) % MOD;
            d -= st[i];
        }

        sol = (sol + currSol) % MOD;
    }
}

void bk(int currDigit, int prod, int sum, int digitsLeft)
{
    if(currDigit == 10)
    {
        CheckSol(prod, sum, digitsLeft);
        return ;
    }

    st[currDigit] = 0;
    bk(currDigit + 1, prod, sum, digitsLeft);

    int pp = prod, ss = sum, dl = digitsLeft;

    for(int i = 1; i <= 20; i++)
        if(pp * currDigit <= 9 * digits)
        {
            st[currDigit] = i;
            pp *= currDigit;
            ss += currDigit;
            dl--;

            if(dl < 0)
                break;

            bk(currDigit + 1, pp, ss, dl);
        }
        else
        {
            break;
        }
}

int main()
{
    cin >> digits;

    if(digits == 1)
    {
        cout << 10 << '\n';
        return 0;
    }

    PrecFact();

    bk(2, 1, 0, digits);

    cout << sol << '\n';

    return 0;
}