#include using namespace std; using ll=long long; template struct Fp{ ll val; constexpr Fp(long long v = 0) noexcept : val(v % MOD) { if (val < 0) val += MOD; } static constexpr int getmod() { return MOD; } constexpr Fp operator - () const noexcept { return val ? MOD - val : 0; } constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; } constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; } constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; } constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; } constexpr Fp& operator += (const Fp& r) noexcept { val += r.val; if (val >= MOD) val -= MOD; return *this; } constexpr Fp& operator -= (const Fp& r) noexcept { val -= r.val; if (val < 0) val += MOD; return *this; } constexpr Fp& operator *= (const Fp& r) noexcept { val = val * r.val % MOD; return *this; } constexpr Fp& operator /= (const Fp& r) noexcept { ll a = r.val, b = MOD, u = 1, v = 0; while (b) { ll t = a / b; a -= t * b, swap(a, b); u -= t * v, swap(u, v); } val = val * u % MOD; if (val < 0) val += MOD; return *this; } constexpr bool operator == (const Fp& r) const noexcept { return this->val == r.val; } constexpr bool operator != (const Fp& r) const noexcept { return this->val != r.val; } constexpr bool operator < (const Fp& r) const noexcept { return this->val < r.val; } friend constexpr istream& operator >> (istream& is, Fp& x) noexcept { is >> x.val; x.val %= MOD; if (x.val < 0) x.val += MOD; return is; } friend constexpr ostream& operator << (ostream& os, const Fp& x) noexcept { return os << x.val; } friend constexpr Fp modpow(const Fp& a, long long n) noexcept { Fp res=1,r=a; while(n){ if(n&1) res*=r; r*=r; n>>=1; } return res; } friend constexpr Fp modinv(const Fp& r) noexcept { long long a = r.val, b = MOD, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b, swap(a, b); u -= t * v, swap(u, v); } return Fp(u); } explicit operator bool()const{ return val; } }; template struct SegmentTree{ int n; vector dat; SegmentTree(int N){ n=1; while(n>=1; dat[k]=op(dat[k*2],dat[k*2+1]); } } void apply(int k,T x){ k+=n; dat[k]=op(dat[k],x); while(k){ k>>=1; dat[k]=op(dat[k*2],dat[k*2+1]); } } void set(int k,T x){ k+=n; dat[k]=x; while(k){ k>>=1; dat[k]=op(dat[k*2],dat[k*2+1]); } } T query(int l,int r){ T prodl=e(),prodr=e(); l+=n; r+=n; while(l>=1; r>>=1; } return op(prodl,prodr); } }; template vector compress(vector &x){ vector vals=x; vector res; sort(vals.begin(),vals.end()); auto it=unique(vals.begin(),vals.end()); vals.erase(it,vals.end()); for(auto xx : x){ int ret=lower_bound(vals.begin(),vals.end(),xx) - vals.begin(); res.push_back(ret); } return res; } using mint=Fp<1000000007>; mint op(mint a,mint b){ return a+b; } mint e(){ return mint(0); } int main(){ int n,k; cin>>n>>k; vector a(n); string s; for(int i=0;i>a[i]; cin>>s; vector A=compress(a); vector> dp(k+1,vector(n)); for(int i=0;i S(n); for(int j=0;j S(n); for(int j=0;j