#define MOD_TYPE 2 #include using namespace std; #include //#include //#include //#include using namespace atcoder; #if 0 #include #include using Int = boost::multiprecision::cpp_int; using lld = boost::multiprecision::cpp_dec_float_100; #endif #if 0 #include #include #include #include using namespace __gnu_pbds; using namespace __gnu_cxx; template using extset = tree, rb_tree_tag, tree_order_statistics_node_update>; #endif #if 1 #pragma GCC target("avx2") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #endif #pragma region Macros using ll = long long int; using ld = long double; using pii = pair; using pll = pair; using pld = pair; template using smaller_queue = priority_queue, greater>; #if MOD_TYPE == 1 constexpr ll MOD = ll(1e9 + 7); #else #if MOD_TYPE == 2 constexpr ll MOD = 998244353; #else constexpr ll MOD = 1000003; #endif #endif using mint = static_modint; constexpr int INF = (int)1e9 + 10; constexpr ll LINF = (ll)4e18; constexpr double PI = acos(-1.0); constexpr double EPS = 1e-11; constexpr int Dx[] = {0, 0, -1, 1, -1, 1, -1, 1, 0}; constexpr int Dy[] = {1, -1, 0, 0, -1, -1, 1, 1, 0}; #define REP(i, m, n) for (ll i = m; i < (ll)(n); ++i) #define rep(i, n) REP(i, 0, n) #define REPI(i, m, n) for (int i = m; i < (int)(n); ++i) #define repi(i, n) REPI(i, 0, n) #define YES(n) cout << ((n) ? "YES" : "NO") << "\n" #define Yes(n) cout << ((n) ? "Yes" : "No") << "\n" #define possible(n) cout << ((n) ? "possible" : "impossible") << "\n" #define Possible(n) cout << ((n) ? "Possible" : "Impossible") << "\n" #define all(v) v.begin(), v.end() #define NP(v) next_permutation(all(v)) #define dbg(x) cerr << #x << ":" << x << "\n"; #define UNIQUE(v) v.erase(unique(all(v)), v.end()) struct io_init { io_init() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << setprecision(30) << setiosflags(ios::fixed); }; } io_init; template inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; } template inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; } inline ll floor(ll a, ll b) { if (b < 0) a *= -1, b *= -1; if (a >= 0) return a / b; return -((-a + b - 1) / b); } inline ll ceil(ll a, ll b) { return floor(a + b - 1, b); } template inline void Fill(A (&array)[N], const T &val) { fill((T *)array, (T *)(array + N), val); } template vector compress(vector &v) { vector val = v; sort(all(val)), val.erase(unique(all(val)), val.end()); for (auto &&vi : v) vi = lower_bound(all(val), vi) - val.begin(); return val; } template constexpr istream &operator>>(istream &is, pair &p) noexcept { is >> p.first >> p.second; return is; } template constexpr ostream &operator<<(ostream &os, pair p) noexcept { os << p.first << " " << p.second; return os; } ostream &operator<<(ostream &os, mint m) { os << m.val(); return os; } ostream &operator<<(ostream &os, modint m) { os << m.val(); return os; } template constexpr istream &operator>>(istream &is, vector &v) noexcept { for (int i = 0; i < v.size(); i++) is >> v[i]; return is; } template constexpr ostream &operator<<(ostream &os, vector &v) noexcept { for (int i = 0; i < v.size(); i++) os << v[i] << (i + 1 == v.size() ? "" : " "); return os; } template constexpr void operator--(vector &v, int) noexcept { for (int i = 0; i < v.size(); i++) v[i]--; } random_device seed_gen; mt19937_64 engine(seed_gen()); struct BiCoef { vector fact_, inv_, finv_; BiCoef(int n) noexcept : fact_(n, 1), inv_(n, 1), finv_(n, 1) { fact_.assign(n, 1), inv_.assign(n, 1), finv_.assign(n, 1); for (int i = 2; i < n; i++) { fact_[i] = fact_[i - 1] * i; inv_[i] = -inv_[MOD % i] * (MOD / i); finv_[i] = finv_[i - 1] * inv_[i]; } } mint C(ll n, ll k) const noexcept { if (n < k || n < 0 || k < 0) return 0; return fact_[n] * finv_[k] * finv_[n - k]; } mint P(ll n, ll k) const noexcept { return C(n, k) * fact_[k]; } mint H(ll n, ll k) const noexcept { return C(n + k - 1, k); } mint Ch1(ll n, ll k) const noexcept { if (n < 0 || k < 0) return 0; mint res = 0; for (int i = 0; i < n; i++) res += C(n, i) * mint(n - i).pow(k) * (i & 1 ? -1 : 1); return res; } mint fact(ll n) const noexcept { if (n < 0) return 0; return fact_[n]; } mint inv(ll n) const noexcept { if (n < 0) return 0; return inv_[n]; } mint finv(ll n) const noexcept { if (n < 0) return 0; return finv_[n]; } }; BiCoef bc(200010); #pragma endregion // ------------------------------- #pragma region FPS // 引用: // https://opt-cp.com/fps-implementation/ #define fastprod 1 #define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i) #define drep(i, n) drep2(i, n, 0) template struct FormalPowerSeries : vector { using vector::vector; using vector::operator=; using F = FormalPowerSeries; F operator-() const { F res(*this); for (auto &e : res) e = -e; return res; } F &operator*=(const T &g) { for (auto &e : *this) e *= g; return *this; } F &operator/=(const T &g) { assert(g != T(0)); *this *= g.inv(); return *this; } F &operator+=(const F &g) { int n = (*this).size(), m = g.size(); repi(i, min(n, m))(*this)[i] += g[i]; return *this; } F &operator-=(const F &g) { int n = (*this).size(), m = g.size(); repi(i, min(n, m))(*this)[i] -= g[i]; return *this; } F &operator<<=(const int d) { int n = (*this).size(); (*this).insert((*this).begin(), d, 0); (*this).resize(n); return *this; } F &operator>>=(const int d) { int n = (*this).size(); (*this).erase((*this).begin(), (*this).begin() + min(n, d)); (*this).resize(n); return *this; } F inv(int d = -1) const { int n = (*this).size(); assert(n != 0 && (*this)[0] != 0); if (d == -1) d = n; assert(d > 0); F res{(*this)[0].inv()}; while (res.size() < d) { int m = size(res); F f(begin(*this), begin(*this) + min(n, 2 * m)); F r(res); f.resize(2 * m), internal::butterfly(f); r.resize(2 * m), internal::butterfly(r); repi(i, 2 * m) f[i] *= r[i]; internal::butterfly_inv(f); f.erase(f.begin(), f.begin() + m); f.resize(2 * m), internal::butterfly(f); repi(i, 2 * m) f[i] *= r[i]; internal::butterfly_inv(f); T iz = T(2 * m).inv(); iz *= -iz; repi(i, m) f[i] *= iz; res.insert(res.end(), f.begin(), f.begin() + m); } return {res.begin(), res.begin() + d}; } // fast: FMT-friendly modulus only #if fastprod F &operator*=(const F &g) { int n = (*this).size(); *this = convolution(*this, g); (*this).resize(n); return *this; } F &operator/=(const F &g) { int n = (*this).size(); *this = convolution(*this, g.inv(n)); (*this).resize(n); return *this; } #else F &operator*=(const F &g) { int n = (*this).size(), m = g.size(); drep(i, n) { (*this)[i] *= g[0]; REPI(j, 1, min(i + 1, m))(*this)[i] += (*this)[i - j] * g[j]; } return *this; } F &operator/=(const F &g) { assert(g[0] != T(0)); T ig0 = g[0].inv(); int n = (*this).size(), m = g.size(); repi(i, n) { REPI(j, 1, min(i + 1, m))(*this)[i] -= (*this)[i - j] * g[j]; (*this)[i] *= ig0; } return *this; } #endif // sparse F &operator*=(vector> g) { int n = (*this).size(); auto [d, c] = g.front(); if (d == 0) g.erase(g.begin()); else c = 0; drep(i, n) { (*this)[i] *= c; for (auto &[j, b] : g) { if (j > i) break; (*this)[i] += (*this)[i - j] * b; } } return *this; } F &operator/=(vector> g) { int n = (*this).size(); auto [d, c] = g.front(); assert(d == 0 && c != T(0)); T ic = c.inv(); g.erase(g.begin()); repi(i, n) { for (auto &[j, b] : g) { if (j > i) break; (*this)[i] -= (*this)[i - j] * b; } (*this)[i] *= ic; } return *this; } // multiply and divide (1 + cz^d) void multiply(const int d, const T c) { int n = (*this).size(); if (c == T(1)) drep(i, n - d)(*this)[i + d] += (*this)[i]; else if (c == T(-1)) drep(i, n - d)(*this)[i + d] -= (*this)[i]; else drep(i, n - d)(*this)[i + d] += (*this)[i] * c; } void divide(const int d, const T c) { int n = (*this).size(); if (c == T(1)) repi(i, n - d)(*this)[i + d] -= (*this)[i]; else if (c == T(-1)) repi(i, n - d)(*this)[i + d] += (*this)[i]; else repi(i, n - d)(*this)[i + d] -= (*this)[i] * c; } T eval(const T &a) const { T x(1), res(0); for (auto e : *this) res += e * x, x *= a; return res; } void differentiate() { int n = (*this).size(); (*this) >>= 1; REPI(i, 1, n - 1)(*this)[i] *= (i + 1); } void integrate(bool ext = true) { if (ext) (*this).push_back(0); int n = (*this).size(); (*this) <<= 1; REPI(i, 1, n)(*this)[i] *= bc.inv(i); } F operator*(const T &g) const { return F(*this) *= g; } F operator/(const T &g) const { return F(*this) /= g; } F operator+(const F &g) const { return F(*this) += g; } F operator-(const F &g) const { return F(*this) -= g; } F operator<<(const int d) const { return F(*this) <<= d; } F operator>>(const int d) const { return F(*this) >>= d; } F operator*(const F &g) const { return F(*this) *= g; } F operator/(const F &g) const { return F(*this) /= g; } F operator*(vector> g) const { return F(*this) *= g; } F operator/(vector> g) const { return F(*this) /= g; } }; using fps = FormalPowerSeries; using sfps = vector>; void add_ext(fps &f, fps &g) { f.resize(max(f.size(), g.size())); f += g; } void prod_ext(fps &f, fps &g) { f.resize(f.size() + g.size() - 1, 0); f *= g; } void prod_ext(fps &f, sfps &g) { int m = 0; for (auto [d, c] : g) { if (m < d) m = d; } f.resize(f.size() + m); f *= g; } #pragma endregion void solve() { int n, k; cin >> n >> k; vector a(n); cin >> a; vector L(n + 1), R(n + 1); fps e(k + 1, 0); e[0] = 1; L[0] = R[n] = e; rep(i, n) { L[i + 1] = L[i]; L[i + 1].multiply(a[i], 1); } for (int i = n; i > 0; i--) { R[i - 1] = R[i]; R[i - 1].multiply(a[i - 1], 1); } if (L[n][k].val() == 0) { cout << -1 << "\n"; return; } int cnt = 0; rep(i, n) { fps f = L[i] * R[i + 1]; if (f[k].val() == 0) cnt++; } cout << cnt << "\n"; } int main() { solve(); }