In our daily life we often use 233 to express our feelings. Actually, we may say 2333, 23333, or 233333 ... in the same meaning. And here is the question: Suppose we have a matrix called 233 matrix. In the first line, it would be 233, 2333, 23333... (it means a _0,1 = 233,a _0,2 = 2333,a _0,3 = 23333...) Besides, in 233 matrix, we got a _i,j = a _i-1,j +a _i,j-1( i,j ≠ 0). Now you have known a _1,0,a_2,0,...,a _n,0, could you tell me a _n,m in the 233 matrix?

1 1

1

2 2

0 0

3 7

23 47 16

234

2799

72937

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<sstream>

#include<algorithm>

#include<queue>

#include<deque>

#include<iomanip>

#include<vector>

#include<cmath>

#include<map>

#include<stack>

#include<set>

#include<fstream>

#include<memory>

#include<list>

#include<string>

using namespace std;

typedef long long LL;

typedef unsigned long long ULL;

#define MAXN 18

#define N 33

#define MOD 10000007

#define INF 1000000009

const double eps = 1e-;

const double PI = acos(-1.0);

/*

组合数学 找规律

递归显然不行，列数太多

只需考虑每个点被加上的次数

a(i,0) = a(i,1) 到 a(n,m) 路径条数（向左和向下两个方向） C(n+m-i-1,n)

发现列数太多没办法打表 再换一种方法

矩阵快速幂

从第一列向后考虑 找出他们的转移矩阵（这里很巧妙的加了一条边 凑2333后面的3）十分巧妙！~

*/

LL a[MAXN], n, m;

struct mat

{

    LL data[MAXN][MAXN];

    mat()

    {

        memset(data, , sizeof(data));

    }

    mat operator*(const mat& rhs)

    {

        mat ret;

        for (int i = ; i <= n + ; i++)

        {

            for (int j = ; j <= n + ; j++)

            {

                for (int k = ; k <= n + ; k++)

                    ret.data[i][j] = (ret.data[i][j] + data[i][k] * rhs.data[k][j]) % MOD;

            }

        }

        return ret;

    }

};

mat fpow(mat a, LL b)

{

    if (b <= ) return a;

    mat tmp = a, ret;

    for (int i = ; i <= n + ; i++)

        ret.data[i][i] = ;

    while (b!= )

    {

        if (b & )

            ret = tmp*ret;

        tmp = tmp*tmp;

        b = b / ;

    }

    return ret;

}

int main()

{

    while (cin >> n >> m)

    {

        a[] = ;

        for (int i = ; i <= n + ; i++)

            cin >> a[i];

        a[n + ] = ;

        mat ans;

        for (int i = ; i <= n + ; i++)

        {

            ans.data[i][] = ;

            ans.data[i][n + ] = ;

            for (int j = ; j <= i; j++)

                ans.data[i][j] = ;

        }

        ans.data[n + ][n + ] = ;

        ans = fpow(ans, m);

        LL result = ;

        for (int i = ; i <= n + ; i++)

            result = (result + a[i] * ans.data[n + ][i]) % MOD;

        cout << result << endl;

    }

    return ;

}