#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; T P; BIT (long long n, T p = 0){ N = n; P = p; bit.resize(N); } void add(long long loc, T val){ loc++; while(loc <= N){ bit[loc-1] += val; if (P) bit[loc-1] %= P; loc += loc & -loc; } } long long sum(long long l, long long r){ T res = _sum(r) - _sum(l-1); if (P) res = (res + P) % P; return res; } long long _sum(long long r){ r++; T res = 0; while(r > 0){ res += bit[r-1]; if (P) 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, modc)); for (int i=0; i