#line 1 "/workspaces/compro/lib/math/modint.hpp" #include #include #include #include #ifndef MOD_INT #define MOD_INT template class ModInt { using u64 = std::uint_fast64_t; public: ModInt(const u64 val = 0) { value = val % MOD; } ModInt operator+(const ModInt rhs) const { return ModInt(*this) += rhs; } ModInt operator-(const ModInt rhs) const { return ModInt(*this) -= rhs; } ModInt operator*(const ModInt rhs) const { return ModInt(*this) *= rhs; } ModInt operator/(const ModInt rhs) const { return ModInt(*this) /= rhs; } ModInt &operator+=(const ModInt rhs) { value += rhs.value; if (value >= MOD) { value -= MOD; } return *this; } ModInt &operator-=(const ModInt rhs) { if (value < rhs.value) { value += MOD; } value -= rhs.value; return *this; } ModInt &operator*=(const ModInt rhs) { value = value * rhs.value % MOD; return *this; } ModInt &operator/=(ModInt rhs) { *this *= rhs.inv(); return *this; } ModInt &operator++(int n) { value++; if (value >= MOD) { value -= MOD; } return *this; } ModInt &operator--(int n) { if (value == 0) { value += MOD; } value--; return *this; } ModInt inv() { return ModInt::pow(*this, MOD - 2); } static ModInt pow(ModInt base, long long int n) { ModInt res = ModInt(1); while (n) { if (n & 1) { res *= base; } base *= base; n /= 2; } return res; } static ModInt comb(ModInt n, ModInt r) { return comb(n.value, r.value); } static ModInt comb(int n, int r) { if (n < r) return ModInt(0); ModInt res = ModInt(1); for (int i = 0; i < r; i++) { res *= ModInt(n - i); } ModInt inv = ModInt(1); for (int i = 0; i < r; i++) { inv *= ModInt(r - i); } return res / inv; } // nC0からnCnまでを計算する。計算量はO(n) // @param n 要素数 // @param vec 結果を格納する配列 static void combination_table(int n, std::vector &vec) { assert(static_cast(vec.size()) >= n + 1); vec[0] = ModInt(1); for (int r = 1; r < n + 1; r++) { vec[r] = vec[r - 1] * ModInt(n - r + 1) / ModInt(r); } } u64 getValue() const { return value; } private: u64 value; friend std::ostream &operator<<(std::ostream &out, const ModInt &m) { out << m.value; return out; } friend std::istream &operator>>(std::istream &in, ModInt &m) { uint_fast64_t i; in >> i; m = ModInt(i); return in; } }; #endif #line 1 "/workspaces/compro/lib/template.hpp" #line 3 "/workspaces/compro/lib/io/vector.hpp" #ifndef IO_VECTOR #define IO_VECTOR template std::ostream &operator<<(std::ostream &out, const std::vector &v) { int size = v.size(); for (int i = 0; i < size; i++) { std::cout << v[i]; if (i != size - 1) std::cout << " "; } return out; } template std::istream &operator>>(std::istream &in, std::vector &v) { for (auto &el : v) { std::cin >> el; } return in; } #endif #line 4 "/workspaces/compro/lib/template.hpp" #include #define REP(i, n) for (int i = 0; i < n; i++) #define FOR(i, m, n) for (int i = m; i < n; i++) #define ALL(v) (v).begin(), (v).end() #define coutd(n) cout << fixed << setprecision(n) #define ll long long int #define vl vector #define vi vector #define MM << " " << using namespace std; template void say(bool val, T yes, T no) { cout << (val ? yes : no) << "\n"; } void say(bool val, string yes = "Yes", string no = "No") { say(val, yes, no); } template void chmin(T &a, T b) { if (a > b) a = b; } template void chmax(T &a, T b) { if (a < b) a = b; } // C++ 17に完全移行したら消す // 最大公約数を求める template T gcd(T n, T m) { return n ? gcd(m % n, n) : m; } // 最小公倍数を求める template T lcm(T n, T m) { int g = gcd(n, m); return n * m / g; } // 重複を消す。計算量はO(NlogN) template void unique(std::vector &v) { std::sort(v.begin(), v.end()); v.erase(std::unique(v.begin(), v.end()), v.end()); } #line 3 "main.cpp" using mint = ModInt<(int)1e9 + 7>; int main() { cin.tie(0); ios::sync_with_stdio(false); int n, k; cin >> n >> k; vi a(n); cin >> a; REP(i, n) { a[i] -= k; } vector> dp(n + 1); dp[0][0] = 1; REP(i, n) { for (const auto [j, val] : dp[i]) { if (!dp[i + 1].count(j + a[i])) dp[i + 1][j + a[i]] = 0; dp[i + 1][j + a[i]] += val; if (!dp[i + 1].count(j)) { dp[i + 1][j] = 0; } dp[i + 1][j] += val; } } mint ans(0); for (const auto [j, val] : dp[n]) { if (j >= 0) ans += val; } cout << ans - 1 << endl; return 0; }