#include #include using namespace atcoder; using namespace std; #define all(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() #define fin(a) return pt(a) using ll=long long; using ld=long double; using v1=vector; using v2=vector; using v3=vector; using v4=vector; using pll=pair; using mll=map; ll inf=1LL<<60; ld pi=acos(-1); ld eps=1e-10; templateusing ascending_priority_queue=std::priority_queue,greater>; templateusing descending_priority_queue=std::priority_queue; templatebool chmax(T&a,const T&b){if(abool chmin(T&a,const T&b){if(bT max(vector&vec,const T&id){T r=id;for(auto&v:vec)chmax(r,max(v,id));return r;} templateT min(vector&vec,const T&id){T r=id;for(auto&v:vec)chmin(r,min(v,id));return r;} templatepll mima(const T&a,const T&b){return {min(a,b),max(a,b)};} templateT sum(vector&a){return accumulate(all(a),T(0));} templateT popcnt(T a){return __builtin_popcountll(a);} istream&operator>>(istream&is,modint1000000007&x){unsigned int t;is>>t;x=t;return is;} istream&operator>>(istream&is,modint998244353&x){unsigned int t;is>>t;x=t;return is;} istream&operator>>(istream&is,modint&x){unsigned int t;is>>t;x=t;return is;} ostream&operator<<(ostream&os,const modint1000000007&x){os<istream&operator>>(istream&is,pair&p){is>>p.first>>p.second;return is;} templateostream&operator<<(ostream&os,const pair&p){os<istream&operator>>(istream&is,vector&v){for(T&x:v)is>>x;return is;} templateostream&operator<<(ostream&os,const vector&v){for(int i=0;i<(int)v.size();i++){os<int pt_rest(){cout<<'\n';return 0;} templateint pt(){cout<<'\n';return 0;} templateint pt_rest(const T&first,const A&...rest){cout<<" "<int pt(const T&first,const A&...rest){cout<void resize(vector&vec,const H head){vec.resize(head);} templatevoid resize(vector&vec,const H&head,const T...tail){vec.resize(head);for(auto&v:vec)resize(v,tail...);} templatevoid fill(V&x,const T&val){x=val;} templatevoid fill(vector&vec,const T&val){for(auto&v:vec)fill(v,val);} templatevoid vin(istream&is,const int idx,vector&head){is>>head[idx];} templatevoid vin(istream&is,const int idx,vector&head,T&...tail){vin(is>>head[idx],idx,tail...);} templatevoid vin(istream&is,vector&head,T&...tail){for(int i=0;i<(int)head.size();i++)vin(is,i,head,tail...);} templatevoid vin(vector&head,T&...tail){vin(cin,head,tail...);} templatevoid sin(istream&is,H&head){is>>head;} templatevoid sin(istream&is,H&head,T&...tail){sin(is>>head,tail...);} templatevoid sin(H&head,T&...tail){sin(cin,head,tail...);} v1 divisor(ll n){mll m;for(ll i=1;i*i<=n;i++)if(n%i==0){m[i]++;m[n/i]++;}v1 v;for(auto[x,_]:m)v.emplace_back(x);return v;} mll factor(ll n){mll m;for(ll i=2;i*i<=n;i++)while(n%i==0){m[i]++;n/=i;}if(n>1)m[n]++;return m;} ll lsqrt(ll x){assert(x>=0);if(x<=1)return x;ll r=sqrt(x)-1;while((r+1)<=x/(r+1))r++;return r;}; using S=ll; S op(S a,S b){return a+b;} S e(){return 0;} int main(void){ cin.tie(nullptr); ios::sync_with_stdio(false); ll N,K;sin(N,K); v1 a(N);cin>>a; using mint=modint1000000007; vector>dp(N+1); dp[0][1]=1; for(ll i=0;i