小明的花店新开张，为了吸引顾客，他想在花店的门口摆上一排花，共m盆。通过调查顾客的喜好，小明列出了顾客最喜欢的nn种花，从1到n标号。为了在门口展出更多种花，规定第ii种花不能超过ai​盆，摆花时同一种花放在一起，且不同种类的花需按标号的从小到大的顺序依次摆列。

试编程计算，一共有多少种不同的摆花方案。

输入格式：

第一行包含两个正整数n和m，中间用一个空格隔开。

第二行有n个整数，每两个整数之间用一个空格隔开，依次表示a_1,a_2,…,a_na1​,a2​,…,an​。

 

一个整数，表示有多少种方案。注意：因为方案数可能很多，请输出方案数对1000007取模的结果。

对于100%数据，有0<n≤100,0<m≤100,0≤a_i≤1000<n≤100,0<m≤100,0≤ai​≤100。

#include<bits/stdc++.h>

using namespace std;

int n,m,a[101],ans[101][101];

int dfs(int q,int w)

{

    if(q==0&&w==0)

    {

        return 1;

    }

    if(w<0||q<=0)

    return 0;

    int ji=0;

    for(int i=0;i<=a[q]&&w-i>=0;i++)

    {

        if(ans[q-1][w-i]==0)

        {

            ans[q-1][w-i]=dfs(q-1,w-i);

        }

        ji+=ans[q-1][w-i];

        ji%=1000007;

    }

    return ji;

}

int main()

{

    cin>>n>>m;

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

    {

        cin>>a[i];

    }

    ans[n][m]=dfs(n,m);

    cout<<ans[n][m]%1000007;

}

记忆化竟然A了！！！