Задача на рекурсию. Сколько существует k-значных натуральных чисел, сумма цифр которых равна s

int f(int l, int s, int d);
int loop(int l, int s, int i) {return i>=10 ? 0 : f(l,s-i,0)+loop(l,s,i+1);}
int f(int l, int s, int d) {return (l<0||s<0) ? 0 : s==0 ? 1 : loop(l-1,s,d);}
int main() {int k,s; cin>>k>>s; cout<<f(k,s,1)<<'\n'; return 0;}

typedef unsigned long long int ull;
ull dp[200][2000][2];
ull f(int l, int s, int d);
ull loop(int l, int s, int i) {return i>=10 ? 0 : f(l-1,s-i,0)+loop(l,s,i+1);}
ull f(int l, int s, int d) {
    if (l<0||s<0||s>l*9) return 0;
    else if (s==0) return 1;
    else {if (dp[l][s][d]==0) dp[l][s][d]=loop(l,s,d); return dp[l][s][d];}
}
int main() {int k,s; cin>>k>>s; cout<<f(k,s,1)<<'\n'; return 0;}

typedef unsigned long long int ull;
 
ull dp[200][2000][2];
 
ull f(int l, int s, int d);
ull loop(int l, int s, int i);
 
int main()
{
    int k,s;
    cin >> k >> s;
    cout << f(k, s, 1) << '\n';
    return 0;
}
 
ull f(int l, int s, int d)
{
    if (l<0 || s<0 || s>l*9)
        return 0;
    else if (s==0)
        return 1;
    else
    {
        if (dp[l][s][d]==0)
            dp[l][s][d] = loop(l, s, d);
        return dp[l][s][d];
    }
}
 
ull loop(int l, int s, int i)
{
    return i >= 10 ? 0 : f(l-1, s-i, 0) + loop(l, s, i+1);
}

#include <iostream>
using namespace std;
typedef unsigned long long int ull;
ull dp[1000][9000][2];
ull f(int, int, int);
ull loop(int l, int s, int i)
{
    if (i>=10)
    {
        return 0;
    }
    else 
    { 
        return f(l-1,s-i,0)+loop(l,s,i+1);
    }
}
ull f(int l, int s, int d)
{
    if (l<0||s<0||s>l*9) return 0;
    else if (s==0) return 1;
    else 
    {
        if (dp[l][s][d]==0)
        {
            dp[l][s][d]=loop(l,s,d);
        }
    return dp[l][s][d];
    }
}
int main()
{
    int n,s;
    std::cin>>n>>s;
    if (s==n*9 || s==1)
        cout<<1;
    else
        cout<<f(n,s,1)%1000000000;
    return 0;
}