Matrix

/*
practice problems : 
problem:  https://codeforces.com/problemset/problem/514/E
solution: https://codeforces.com/contest/514/submission/183516372
problem:  https://codeforces.com/problemset/problem/392/C
/**/

#define int long long 
#define ll long long 

const int N = 103; 

int sum(ll x, ll y)
{
    x += y;
    if (x >= MOD)
        return x - MOD;
    return x;
}
int mult(ll x, ll y)
{
    x%=MOD ;
    y%=MOD ;
    return (x * y) % MOD;
}

struct Matrix
{
    ll a[N+1][N+1];
    Matrix()
    {
        for (int i = 1; i <=N; i++)
            for (int j = 1; j <=N; j++)
                a[i][j] = 0;
    }
    Matrix operator * (const Matrix &X) const
    {
        Matrix res;
        for (int i = 1; i <= N; i++)
            for (int j = 1; j <= N; j++)
            {
                res.a[i][j] = 0;
                for (int h = 1; h <=N; h++)
                {
                    res.a[i][j] = sum(res.a[i][j], mult(a[i][h], X.a[h][j]));
                }
            }
        return res;
    }
};

Matrix bin_pow(Matrix x, ll pow)
{
    if (pow == 1) return x;
    if (pow == 2) return x * x;
    if (pow & 1) return x * bin_pow(x, pow - 1);
    return bin_pow(bin_pow(x, pow / 2), 2);
}

Matrix generate()  // make your own matrix...  
{
    Matrix A;

    for(int i=2;i<=100;++i)
        A.a[i][i-1]=1 ;

    for(int i=1;i<=100;++i)
        A.a[i][100]=A.a[i][101]=cnt[100-i+1] ;

    A.a[101][101]=1 ;

    return A;
}



----------------------------------------------------------------------
// template ends here.
// you can ignore...