#include #pragma GCC diagnostic ignored "-Wsign-compare" #pragma GCC diagnostic ignored "-Wsign-conversion" //!===========================================================!// //! dP dP dP !// //! 88 88 88 !// //! 88aaaaa88a .d8888b. .d8888b. .d888b88 .d8888b. 88d888b. !// //! 88 88 88ooood8 88' '88 88' '88 88ooood8 88' '88 !// //! 88 88 88. ... 88. .88 88. .88 88. ... 88 !// //! dP dP '88888P' '88888P8 '88888P8 '88888P' dP !// //!===========================================================!// using ld = long double; using ll = long long; using ull = unsigned long long; std::mt19937 mt{std::random_device{}()}; template constexpr T INF = std::numeric_limits::max() / 4; template constexpr T MOD = static_cast(1000000007); template constexpr F PI() { return 3.1415926535897932385; } #define SHOW(...) (std::cerr << "(" << #__VA_ARGS__ << ") = ("), HogeHogeSansuu(__VA_ARGS__), std::cerr << ")" << std::endl; struct has_debugPrint_impl { template static auto check(T&& x) -> decltype(x.debugPrint(), std::true_type{}); template static auto check(...) -> std::false_type; }; template class has_debugPrint : public decltype(has_debugPrint_impl::check(std::declval())) { }; template struct HogeHogeDump { template static void dump(const T& x) { x.debugPrint(); } }; template <> struct HogeHogeDump { template static void dump(const T& x) { std::cerr << x; } }; void HogeHogeSansuu() { ; } template void HogeHogeSansuu(const T& x) { HogeHogeDump::value>::dump(x); } template void HogeHogeSansuu(const T& x, Args... args) { HogeHogeDump::value>::dump(x), std::cerr << ",", HogeHogeSansuu(args...); } template bool chmin(T& a, const T& b) { return a = std::min(a, b), a == b; } template bool chmax(T& a, const T& b) { return a = std::max(a, b), a == b; } template void For(const T s, const T t, const F f) { for (T i = s; i != t; i += T(s < t ? 1 : -1)) { f(i); } } template void Rep(const T N, const F f) { For(0, N, f); } template void RRep(const T N, const F f) { For(N - 1, -1, f); } template std::vector Vec(const std::size_t n, T v) { return std::vector(n, v); } template auto Vec(const std::size_t n, Args... args) { return std::vector(n, Vec(args...)); } template constexpr T PopCount(T v) { return v = (v & 0x5555555555555555ULL) + (v >> 1 & 0x5555555555555555ULL), v = (v & 0x3333333333333333ULL) + (v >> 2 & 0x3333333333333333ULL), v = (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL, static_cast(v * 0x0101010101010101ULL >> 56 & 0x7f); } template constexpr T log2p1(T v) { return v |= (v >> 1), v |= (v >> 2), v |= (v >> 4), v |= (v >> 8), v |= (v >> 16), v |= (v >> 32), PopCount(v); } template constexpr bool ispow2(const T v) { return (v << 1) == (T(1) << (log2p1(v))); } template constexpr T ceil2(const T v) { return ispow2(v) ? v : T(1) << log2p1(v); } template constexpr T floor2(const T v) { return v == 0 ? T(0) : ispow2(v) ? v : T(1) << (log2p1(v) - 1); } template struct Accum { template Accum(const InIt first, const InIt last) : accum(std::size_t(std::distance(first, last))) { std::partial_sum(first, last, accum.begin()); } T sum(const std::size_t i) const { return i == 0 ? T(0) : accum[i - 1]; } T sum(const std::size_t l, const std::size_t r) const { return sum(r) - sum(l); } std::vector accum; }; template struct Accum2D { Accum2D(const std::vector>& t) : accum{t} { for (std::size_t i = 0; i < accum.size(); i++) { for (std::size_t j = 1; j < accum[i].size(); j++) { accum[i][j] += accum[i][j - 1]; } } for (std::size_t i = 1; i < accum.size(); i++) { for (std::size_t j = 0; j < accum[i].size(); j++) { accum[i][j] += accum[i - 1][j]; } } } T sum(const std::size_t y, const std::size_t x) const { return y == 0 or x == 0 ? T(0) : accum[y - 1][x - 1]; } T sum(const std::size_t ymin, const std::size_t ysup, const std::size_t xmin, const std::size_t xsup) const { return sum(ysup, xsup) - sum(ymin, xmin); } std::vector> accum; }; template struct Zip { template Zip(const InIt first, const InIt last) : unzip(std::size_t(std::distance(first, last))) { std::copy(first, last, unzip), std::sort(unzip.begin(), unzip.end()), unzip.erase(std::unique(unzip.begin(), unzip.end()), unzip.end()); for (std::size_t i = 0; i < unzip.size(); i++) { zip[unzip[i]] = i; } } std::vector unzip; std::map zip; }; template std::ostream& operator<<(std::ostream& os, const std::array& v) { os << "["; for (const auto& e : v) { os << e << ","; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::deque& v) { os << "["; for (const auto& e : v) { os << e << ","; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::multimap& v) { os << "["; for (const auto& e : v) { os << "<" << e.first << ": " << e.second << ">,"; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::multiset& v) { os << "["; for (const auto& e : v) { os << e << ","; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::map& v) { os << "["; for (const auto& e : v) { os << "<" << e.first << ": " << e.second << ">,"; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::pair& v) { return (os << "<" << v.first << "," << v.second << ">"); } template std::ostream& operator<<(std::ostream& os, const std::priority_queue& v) { auto q = v; os << "["; while (not q.empty()) { os << q.top() << ",", q.pop(); } return os << "]\n"; } template std::ostream& operator<<(std::ostream& os, const std::queue& v) { auto q = v; os << "["; while (not q.empty()) { os << q.front() << ",", q.pop(); } return os << "]\n"; } template std::ostream& operator<<(std::ostream& os, const std::set& v) { os << "["; for (const auto& e : v) { os << e << ","; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::stack& v) { auto q = v; os << "["; while (not q.empty()) { os << q.top() << ",", q.pop(); } return os << "]\n"; } template std::ostream& operator<<(std::ostream& os, const std::unordered_multimap& v) { os << "["; for (const auto& e : v) { os << "<" << e.first << ": " << e.second << ">,"; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::unordered_multiset& v) { os << "["; for (const auto& e : v) { os << e << ","; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::unordered_map& v) { os << "["; for (const auto& e : v) { os << "<" << e.first << ": " << e.second << ">,"; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::unordered_set& v) { os << "["; for (const auto& e : v) { os << e << ","; } return (os << "]" << std::endl); } template std::ostream& operator<<(std::ostream& os, const std::vector& v) { os << "["; for (const auto& e : v) { os << e << ","; } return (os << "]" << std::endl); } //!===============================================================!// //! 88888888b dP .88888. a88888b. 888888ba !// //! 88 88 d8' '88 d8' '88 88 '8b !// //! a88aaaa dP. .dP d8888P 88 88 88 88 !// //! 88 '8bd8' 88 88 YP88 88 88 88 !// //! 88 .d88b. 88 Y8. .88 Y8. .88 88 .8P !// //! 88888888P dP' 'dP dP '88888' Y88888P' 8888888P !// //!===============================================================!// template constexpr std::pair extgcd(const T a, const T b) { if (b == 0) { return std::pair{1, 0}; } const auto p = extgcd(b, a % b); return {p.second, p.first - p.second * (a / b)}; } template constexpr T inverse(const T a, const T mod) { return (mod + extgcd((mod + a % mod) % mod, mod).first % mod) % mod; } //!========================================================!// //! 8888ba.88ba dP dP dP !// //! 88 '8b '8b 88 88 88 !// //! 88 88 88 .d8888b. .d888b88 88 88d888b. d8888P !// //! 88 88 88 88' '88 88' '88 88 88' '88 88 !// //! 88 88 88 88. .88 88. .88 88 88 88 88 !// //! dP dP dP '88888P' '88888P8 dP dP dP dP !// //!========================================================!// template class ModInt { private: T value; public: ModInt() : value{0} {} ModInt(const T val) : value{((val % mod) + mod) % mod} {} ModInt(const ModInt& n) : value{n()} {} ModInt& operator=(const ModInt& n) { return value = n(), (*this); } ModInt& operator=(const T v) { return value = (mod + v % mod) % mod, (*this); } ModInt operator+() const { return *this; } ModInt operator-() const { return ModInt{mod - value}; } ModInt operator+(const ModInt& val) const { return ModInt{value + val()}; } ModInt operator-(const ModInt& val) const { return ModInt{value - val() + mod}; } ModInt operator*(const ModInt& val) const { return ModInt{value * val()}; } ModInt operator/(const ModInt& val) const { return ModInt{value * inverse(val(), mod)}; } ModInt& operator+=(const ModInt& val) { return (((value += val()) %= mod) += mod) %= mod, (*this); } ModInt& operator-=(const ModInt& val) { return (((value -= val()) %= mod) += mod) %= mod, (*this); } ModInt& operator*=(const ModInt& val) { return (((value *= val()) %= mod) += mod) %= mod, (*this); } ModInt& operator/=(const ModInt& val) { return (((value *= inverse(val(), mod)) %= mod) += mod) %= mod, (*this); } ModInt operator+(const T val) const { return ModInt{value + val}; } ModInt operator-(const T val) const { return ModInt{value - val}; } ModInt operator*(const T val) const { return ModInt{value * val}; } ModInt operator/(const T val) const { return ModInt{value * inverse(val, mod)}; } template ModInt operator^(const I n) const { return n < 0 ? (T(1) / (*this)) ^ (-n) : n == 0 ? ModInt(1) : n % 2 == 1 ? (*this) * ((*this) ^ (n - 1)) : ((*this * *this) ^ (n / 2)); } ModInt& operator+=(const T val) { return (((value += val) %= mod) += mod) %= mod, (*this); } ModInt& operator-=(const T val) { return (((value -= val) %= mod) += mod) %= mod, (*this); } ModInt& operator*=(const T val) { return (((value *= val) %= mod) += mod) %= mod, (*this); } ModInt& operator/=(const T val) { return (((value *= inverse(val, mod)) %= mod) += mod) %= mod, (*this); } template ModInt& operator^=(const I n) { return (*this) = ((*this) ^ n); } bool operator==(const ModInt& val) const { return value == val.value; } bool operator!=(const ModInt& val) const { return not(*this == val); } bool operator==(const T val) const { return value == (mod + val % mod) % mod; } bool operator!=(const T val) const { return not(*this == val); } T operator()() const { return value; } }; template inline ModInt operator+(const T val, const ModInt& n) { return ModInt{n() + val}; } template inline ModInt operator-(const T val, const ModInt& n) { return ModInt{-n() + val}; } template inline ModInt operator*(const T val, const ModInt& n) { return ModInt{n() * val}; } template inline ModInt operator/(const T val, const ModInt& n) { return ModInt(val) / n; } template inline bool operator==(const T val, const ModInt& n) { return n == val; } template inline bool operator!=(const T val, const ModInt& n) { return not(val == n); } template inline std::istream& operator>>(std::istream& is, ModInt& n) { T v; return is >> v, n = v, is; } template std::ostream& operator<<(std::ostream& os, const ModInt& n) { return (os << n()); } template using Mint = ModInt; template using Mll = ModInt; //!=====================================================!// //! 8888ba.88ba dP oo !// //! 88 '8b '8b 88 !// //! 88 88 88 .d8888b. d8888P 88d888b. dP dP. .dP !// //! 88 88 88 88' '88 88 88' '88 88 '8bd8' !// //! 88 88 88 88. .88 88 88 88 .d88b. !// //! dP dP dP '88888P8 dP dP dP dP' 'dP !// //!=====================================================!// template struct Matrix { Matrix(const std::size_t R, const std::size_t C) : R{R}, C{C}, table(R, std::vector(C, T(0))) {} const std::vector& operator[](const std::size_t r) const { return table[r]; } std::vector& operator[](const std::size_t r) { return table[r]; } Matrix operator-() const { Matrix ans(R, C); for (std::size_t i = 0; i < R; i++) { for (std::size_t j = 0; j < C; j++) { ans[i][j] = -table[i][j]; } } return ans; } Matrix operator+(const Matrix& m) const { assert(R == m.R and C == m.C); Matrix ans(R, C); for (std::size_t i = 0; i < R; i++) { for (std::size_t j = 0; j < C; j++) { ans[i][j] = table[i][j] + m[i][j]; } } return ans; } Matrix operator-(const Matrix& m) const { assert(R == m.R and C == m.C); Matrix ans(R, C); for (std::size_t i = 0; i < R; i++) { for (std::size_t j = 0; j < C; j++) { ans[i][j] = table[i][j] - m[i][j]; } } return ans; } Matrix operator*(const Matrix& m) const { assert(C == m.R); Matrix ans(R, m.C); for (std::size_t i = 0; i < R; i++) { for (std::size_t j = 0; j < m.C; j++) { for (std::size_t k = 0; k < C; k++) { ans[i][j] += table[i][k] * m[k][j]; } } } return ans; } Matrix operator*(const T& t) const { Matrix ans(R, C); for (std::size_t i = 0; i < R; i++) { for (std::size_t j = 0; j < C; j++) { ans[i][j] = table[i][j] * t; } } return ans; } template Matrix operator^(const C n) const { return assert(n > 0), n == 1 ? *this : n % 2 == 1 ? (*this) * ((*this) ^ (n - 1)) : (((*this) * (*this)) ^ (n / 2)); } Matrix& operator=(const Matrix& m) { assert(R == m.R and C == m.C); for (std::size_t i = 0; i < R; i++) { for (std::size_t j = 0; j < C; j++) { table[i][j] = m[i][j]; } } return *this; } Matrix& operator+=(const Matrix& m) { assert(R == m.R and C == m.C); for (std::size_t i = 0; i < R; i++) { for (std::size_t j = 0; j < C; j++) { table[i][j] += m[i][j]; } } } Matrix& operator-=(const Matrix& m) { assert(R == m.R and C == m.C); for (std::size_t i = 0; i < R; i++) { for (std::size_t j = 0; j < C; j++) { table[i][j] -= m[i][j]; } } return *this; } Matrix& operator*=(const Matrix& m) { return *this = (*this) * m; } Matrix& operator*=(const T& t) { for (std::size_t i = 0; i < R; i++) { for (std::size_t j = 0; j < C; j++) { table[i][j] *= t; } } return *this; } template Matrix& operator^=(const C n) { return (*this) = ((*this) ^ n); } const std::size_t R, C; std::vector> table; }; template Matrix operator*(const T& t, const Matrix& m) { return m * t; } template std::ostream& operator<<(std::ostream& os, const Matrix& m) { os << "[\n"; for (std::size_t i = 0; i < m.R; i++) { os << "["; for (std::size_t j = 0; j < m.C; j++) { os << m[i][j] << " "; } os << "]\n"; } return (os << "]\n"); } template struct Vector { Vector(const std::size_t R) : R{R}, table(R, T(0)) {} const T& operator[](const std::size_t r) const { return table[r]; } T& operator[](const std::size_t r) { return table[r]; } Vector operator+(const Vector& v) const { assert(R == v.R); Vector ans(R); for (std::size_t i = 0; i < R; i++) { ans[i] = table[i] + v[i]; } return ans; } Vector operator-(const Vector& v) const { assert(R == v.R); Vector ans(R); for (std::size_t i = 0; i < R; i++) { ans[i] = table[i] - v[i]; } return ans; } Vector operator*(const T& t) const { Vector ans(R); for (std::size_t i = 0; i < R; i++) { ans[i] = table[i] * t; } return ans; } Vector& operator=(const Vector& v) { assert(R == v.R); for (std::size_t i = 0; i < R; i++) { table[i] = v[i]; } return *this; } Vector& operator+=(const Vector& v) { assert(R == v.R); for (std::size_t i = 0; i < R; i++) { table[i] += v[i]; } return *this; } Vector& operator-=(const Vector& v) { assert(R == v.R); for (std::size_t i = 0; i < R; i++) { table[i] -= v[i]; } return *this; } Vector& operator*=(const T& t) { Vector ans(R); for (std::size_t i = 0; i < R; i++) { table[i] *= t; } return *this; } const std::size_t R; std::vector table; }; template Vector operator*(const T& t, const Vector& v) { return v * t; } template Vector operator*(const Matrix& m, const Vector& v) { assert(m.C == v.R); Vector ans(m.R); for (std::size_t i = 0; i < m.R; i++) { for (std::size_t j = 0; j < m.C; j++) { ans[i] += m[i][j] * v[j]; } } return ans; } template std::ostream& operator<<(std::ostream& os, const Vector& v) { os << "[\n"; for (std::size_t i = 0; i < v.R; i++) { os << v[i] << "\n"; } return (os << "]\n"); } template struct TVector { TVector(const std::size_t C) : C{C}, table(C, T(0)) {} const T& operator[](const std::size_t c) const { return table[c]; } T& operator[](const std::size_t c) { return table[c]; } TVector operator+(const TVector& v) const { assert(C == v.C); TVector ans(C); for (std::size_t i = 0; i < C; i++) { ans[i] = table[i] + v[i]; } return ans; } TVector operator-(const TVector& v) const { assert(C == v.C); TVector ans(C); for (std::size_t i = 0; i < C; i++) { ans[i] = table[i] - v[i]; } return ans; } TVector operator*(const T& t) const { TVector ans(C); for (std::size_t i = 0; i < C; i++) { ans[i] = table[i] * t; } return ans; } TVector& operator=(const TVector& v) { assert(C == v.C); for (std::size_t i = 0; i < C; i++) { table[i] = v[i]; } return *this; } TVector& operator+=(const TVector& v) { assert(C == v.C); for (std::size_t i = 0; i < C; i++) { table[i] += v[i]; } return *this; } TVector& operator-=(const TVector& v) { assert(C == v.C); for (std::size_t i = 0; i < C; i++) { table[i] -= v[i]; } return *this; } TVector& operator*=(const T& t) { TVector ans(C); for (std::size_t i = 0; i < C; i++) { table[i] *= t; } return *this; } const std::size_t C; std::vector table; }; template TVector operator*(const T& t, const TVector& v) { return v * t; } template TVector operator*(const TVector& v, const Matrix& m) { assert(v.C == m.R); TVector ans(m.C); for (std::size_t i = 0; i < m.C; i++) { for (std::size_t j = 0; j < m.R; j++) { ans[i] += v[j] * m[j][i]; } } return ans; } template std::ostream& operator<<(std::ostream& os, const TVector& v) { os << "[ "; for (std::size_t i = 0; i < v.C; i++) { os << v[i] << " "; } return (os << "]\n"); } //!============================================!// //! 8888ba.88ba oo !// //! 88 '8b '8b !// //! 88 88 88 .d8888b. dP 88d888b. !// //! 88 88 88 88' '88 88 88' '88 !// //! 88 88 88 88. .88 88 88 88 !// //! dP dP dP '88888P8 dP dP dP !// //!============================================!// using mll = ModInt>; using Mat = Matrix; int main() { int N; ll C; std::cin >> N >> C; std::vector a(N); for (int i = 0; i < N; i++) { std::cin >> a[i]; } Mat m(N, N); for (int i = 0; i < N; i++) { for (int j = 0; j <= i; j++) { m[i][j] = a[j]; } } m ^= C; mll ans = 0; for (int i = 0; i < N; i++) { ans += m[N - 1][i] - (a[i] ^ C); } std::cout << ans << std::endl; return 0; }