Number Formation

Number Formation

Given three integers x,y and z you need to find the sum of all the numbers formed by having 4 atmost x times , having 5 atmost y times and having 6 atmost z times as a digit.

Note : Output the sum modulo 10^9+7.

Let us consider dp(x,y,z)  represents the sum of all numbers formed using 4 number of 's, 5 number of 's and 6 number of 's.
So, the required value can be calculated as given below.

for (int i = 0; i <= x; ++ i) 
    for (int j = 0; j <= y; ++ j) 
      for (int k = 0; k <= z; ++ k) 
            ans+=dp(i,j,k);

Now, let us see how to calculate the value of f(x,y,z). Let us consider that g(x,y,z) represents number of numbers which
 have x number of 4's, y number of 5's and z number of 6's.

#include <iostream>
using namespace std;
#define lld long long int

lld dp[101][101][101],cnt[101][101][101];

int main()
{
    int t;
    cin>>t;
    for(int i1=0;i1<101;i1++)
    {
        for(int i2=0;i2<101;i2++)
        {
            for(int i3=0;i3<101;i3++)
            {
                dp[i1][i2][i3]=0;
                cnt[i1][i2][i3]=(!i1 && !i2 && !i3);
                if(i1)
                {
                    dp[i1][i2][i3]=(dp[i1][i2][i3]+10*dp[i1-1][i2][i3]+4*cnt[i1-1][i2][i3])%1000000007;
                    cnt[i1][i2][i3]=(cnt[i1][i2][i3]+cnt[i1-1][i2][i3])%1000000007;
                }
                if(i2)
                {
                    dp[i1][i2][i3]=(dp[i1][i2][i3]+10*dp[i1][i2-1][i3]+5*cnt[i1][i2-1][i3])%1000000007;
                    cnt[i1][i2][i3]=(cnt[i1][i2][i3]+cnt[i1][i2-1][i3])%1000000007;
                }
                if(i3)
                {
                    dp[i1][i2][i3]=(dp[i1][i2][i3]+10*dp[i1][i2][i3-1]+6*cnt[i1][i2][i3-1])%1000000007;
                    cnt[i1][i2][i3]=(cnt[i1][i2][i3]+cnt[i1][i2][i3-1])%1000000007;
                }
            }
        }
    }
    for(int iter=0;iter<t;iter++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        lld sum=0;
        for(int i1=0;i1<=x;i1++)
        {
            for(int i2=0;i2<=y;i2++)
            {
                for(int i3=0;i3<=z;i3++)
                {
                sum=(sum+dp[i1][i2][i3])%1000000007;
                }
            }
        }
        cout<<sum<<endl;
    }
    return 0;
}