#include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; template struct BIT { vector bit; long long N; const T P=1e9+7; BIT (long long n){ N = n; bit.resize(N); } void add(long long loc, T val){ loc++; while(loc <= N){ bit[loc-1] += val; bit[loc-1] %= P; loc += loc & -loc; } } long long sum(long long l, long long r){ T res = _sum(r) - _sum(l-1); res = (res + P) % P; return res; } long long _sum(long long r){ r++; T res = 0; while(r > 0){ res += bit[r-1]; res %= P; r -= r & -r; } return res; } }; template void compress(vector &A){ map comp; int N = A.size(), i=0; for (int i=0; i> N >> K; vector A(N); for (int i=0; i> A[i]; cin >> S; compress(A); vector> dp(K+1, BIT(N)); for (int i=0; i