#include #include using mint = atcoder::static_modint<2>; using namespace std; template struct Matrix : public std::vector> { Matrix() = default; Matrix(int h, int w, const T& v) : std::vector>(h, std::vector(w, v)) {} Matrix(int h, int w) : Matrix(h, w, T{}) {} Matrix(const std::vector>& V) : std::vector>(V) {} Matrix(std::vector>&& V) : std::vector>(std::move(V)) {} static Matrix eye(int sz) { Matrix res(sz, sz); for (int i = 0; i < sz; i++) res[i][i] = 1; return res; } int height() const { return this->size(); } int width() const { return this->size() ? (*this)[0].size() : 0; } bool is_square() const { return height() == width(); } Matrix& operator+=(const Matrix& other) { assert(height() == other.height() && width() == other.width()); for (int i = 0; i < height(); i++) for (int j = 0; j < width(); j++) { (*this)[i][j] += other[i][j]; } return *this; } Matrix& operator-=(const Matrix& other) { assert(height() == other.height() && width() == other.width()); for (int i = 0; i < height(); i++) for (int j = 0; j < width(); j++) { (*this)[i][j] -= other[i][j]; } return *this; } Matrix& operator*=(const Matrix& other) { assert(width() == other.height()); Matrix res(height(), other.width()); for (int i = 0; i < height(); i++) { for (int k = 0; k < width(); k++) { for (int j = 0; j < other.width(); j++) { res[i][j] += (*this)[i][k] * other[k][j]; } } } return *this = std::move(res); } Matrix& operator*=(T s) { for (int i = 0; i < height(); i++) { for (int j = 0; j < width(); j++) { (*this)[i][j] *= s; } } return *this; } friend Matrix operator+(const Matrix& lhs, const Matrix& rhs) { return Matrix(lhs) += rhs; } friend Matrix operator-(const Matrix& lhs, const Matrix& rhs) { return Matrix(lhs) -= rhs; } friend Matrix operator*(const Matrix& lhs, const Matrix& rhs) { return Matrix(lhs) *= rhs; } friend Matrix operator*(const Matrix& lhs, T rhs) { return Matrix(lhs) *= rhs; } friend Matrix operator*(int lhs, const Matrix& rhs) { return Matrix(rhs) *= lhs; } Matrix pow(long long b) const { Matrix a = *this, res = eye(height()); while (b) { if (b & 1) res *= a; a *= a; b >>= 1; } return res; } Matrix transpose() const { Matrix res(width(), height()); for (int i = 0; i < height(); i++) { for (int j = 0; j < width(); j++) { res[j][i] = (*this)[i][j]; } } return res; } }; int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); std::fixed(std::cout).precision(16); long long N, K; cin >> N >> K; vector A(N); for (int i = 0; i < N; i++) cin >> A[i]; if (K <= N) cout << (A[K - 1]) << "\n"; else { long long ans = 0; for (int it = 0; it <= 60; it++) { Matrix a(N, N); for (int j = 0; j < N; j++) a[0][j] = 1; for (int j = 0; j < N - 1; j++) a[j + 1][j] = 1; a = a.pow(K - N); mint t = 0; for (int i = 0; i < N; i++) t += a[0][i] * (A[i] >> it & 1); if (t.val()) ans += 1LL << it; } cout << ans << "\n"; } return 0; }