// includes #include using namespace std; // macros #define pb emplace_back #define mk make_pair #define FOR(i, a, b) for(int i=(a);i<(b);++i) #define rep(i, n) FOR(i, 0, n) #define rrep(i, n) for(int i=((int)(n)-1);i>=0;i--) #define irep(itr, st) for(auto itr = (st).begin(); itr != (st).end(); ++itr) #define irrep(itr, st) for(auto itr = (st).rbegin(); itr != (st).rend(); ++itr) #define all(x) (x).begin(),(x).end() #define sz(x) ((int)(x).size()) #define UNIQUE(v) v.erase(unique(v.begin(), v.end()), v.end()) #define bit(n) (1LL<<(n)) // functions template bool chmax(T &a, const T &b){if(a < b){a = b; return 1;} return 0;} template bool chmin(T &a, const T &b){if(a > b){a = b; return 1;} return 0;} template istream &operator>>(istream &is, vector &vec){for(auto &v: vec)is >> v; return is;} template ostream &operator<<(ostream &os, const vector& vec){for(int i = 0; i < vec.size(); i++){ os << vec[i]; if(i + 1 != vec.size())os << " ";} return os;} template ostream &operator<<(ostream &os, const set& st){for(auto itr = st.begin(); itr != st.end(); ++itr){ os << *itr; auto titr = itr; if(++titr != st.end())os << " ";} return os;} template ostream &operator<<(ostream &os, const unordered_set& st){for(auto itr = st.begin(); itr != st.end(); ++itr){ os << *itr; auto titr = itr; if(++titr != st.end())os << " ";} return os;} template ostream &operator<<(ostream &os, const multiset& st){for(auto itr = st.begin(); itr != st.end(); ++itr){ os << *itr; auto titr = itr; if(++titr != st.end())os << " ";} return os;} template ostream &operator<<(ostream &os, const unordered_multiset& st){for(auto itr = st.begin(); itr != st.end(); ++itr){ os << *itr; auto titr = itr; if(++titr != st.end())os << " ";} return os;} template ostream &operator<<(ostream &os, const pair &p){os << p.first << " " << p.second; return os;} template ostream &operator<<(ostream &os, const map &mp){for(auto itr = mp.begin(); itr != mp.end(); ++itr){ os << itr->first << ":" << itr->second; auto titr = itr; if(++titr != mp.end())os << " "; } return os;} template ostream &operator<<(ostream &os, const unordered_map &mp){for(auto itr = mp.begin(); itr != mp.end(); ++itr){ os << itr->first << ":" << itr->second; auto titr = itr; if(++titr != mp.end())os << " "; } return os;} // types using ll = long long int; using P = pair; // constants const int inf = 1e9; const ll linf = 1LL << 50; const double EPS = 1e-10; const int mod = 1000000007; const int dx[4] = {-1, 0, 1, 0}; const int dy[4] = {0, -1, 0, 1}; // io struct fast_io{ fast_io(){ios_base::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(20);} } fast_io_; template T extgcd(T a, T b, T &x, T &y){ T d = a; if(b != 0){ d = extgcd(b, a % b, y, x); y -= (a / b) * x; }else{ x = 1, y = 0; } return d; } template T modinv(T a, T m){ long long x = 0, y = 0; extgcd(a, m, x, y); x %= m; if(x < 0)x += m; return x; } template struct LMatrix{ vector> v; int n, m; LMatrix(int n_, int m_ = -1): n(n_), m(m_){ if(m < 0)m = n; v.resize(n); for(int i = 0; i < n; i++)v[i].resize(m); } void identity(){ assert(n == m); for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ v[i][j] = (i == j ? 1: 0); } } } vector &operator[](size_t i){ return v[i]; } const vector &operator[](size_t i) const{ return v[i]; } LMatrix operator*(const LMatrix &r) const{ assert(m == r.n); int l = r.m; LMatrix res(n, l); for(int i = 0; i < n; i++){ for(int j = 0; j < l; j++){ res.v[i][j] = 0; for(int k = 0; k < m; k++){ res.v[i][j] = (res.v[i][j] + v[i][k] * r.v[k][j] % MOD) % MOD; } } } return res; } LMatrix operator+(const LMatrix &r) const{ assert(n == r.n); assert(m == r.m); LMatrix res(n, m); for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ res[i][j] = (v[i][j] + r[i][j]) % MOD; } } return res; } LMatrix operator-(const LMatrix &r) const{ assert(n == r.n); assert(m == r.m); LMatrix res(n, m); for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ res[i][j] = (v[i][j] - r[i][j]) % MOD; if(res[i][j] < 0)res[i][j] += MOD; } } return res; } template LMatrix operator*(T a) const{ LMatrix res = *this; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ res[i][j] = a * res[i][j] % MOD; } } return res; } LMatrix inv2() const{ assert(n == 2 && m == 2); long long det = v[0][0] * v[1][1] % MOD - v[0][1] * v[1][0] % MOD; if(det < 0)det += MOD; assert(det != 0); LMatrix res(2, 2); long long inv = modinv(det, (long long)MOD); res[0][0] = v[1][1]; res[1][1] = v[0][0]; res[1][0] = - v[1][0]; res[0][1] = - v[0][1]; for(int i = 0; i < n; i++){ for(int j = 0; j < m; j++){ res[i][j] %= MOD; res[i][j] = res[i][j] * inv % MOD; if(res[i][j] < 0)res[i][j] += MOD; } } return res; } }; template LMatrix operator*(T a, const LMatrix b){ return b * a; } template LMatrix powerm(LMatrix &a, long long n){ long long tmp = n; LMatrix curr = a; LMatrix res(a.n); res.identity(); while(tmp){ if(tmp % 2 == 1){ res = res * curr; } curr = curr * curr; tmp /= 2; } return res; } int main(int argc, char const* argv[]) { int n; cin >> n; ll k; cin >> k; vector a(n); cin >> a; --k; if(k <= 1000000){ if(k < n){ ll sum = 0; rep(i, k)sum = (sum + a[i]) % mod; cout << a[k] << " " << sum << endl; return 0; } vector b(k + 1); rep(i, n){ b[i] = a[i]; b[n] += b[i]; } b[n] %= mod; for(int i = n + 1; i <= k; i++){ b[i] = (b[i-1] + b[i-1] - b[i-n-1]) % mod; } if(b[k] < 0)b[k] += mod; ll sum = 0; rep(i, k + 1)sum = (sum + b[i]) % mod; if(sum < 0)sum += mod; cout << b[k] << " " << sum << endl; }else{ if(k < n){ ll sum = 0; rep(i, k)sum = (sum + a[i]) % mod; cout << a[k] << " " << sum << endl; return 0; } LMatrix<> lm(n + 1, n + 1); rep(i, n)lm[0][i] = 1; FOR(i, 1, n){ lm[i][i-1] = 1; } rep(i, n + 1)lm[n][i] = 1; auto p = powerm(lm, k - n + 1); ll f = 0, s = 0; rep(i, n)f = (f + p[0][i] * a[n-1-i] % mod) % mod; rep(i, n)s = (s + p[n][i] * a[n-1-i] % mod) % mod; ll S = 0; rep(i, n)S += a[i]; f = (f + p[0][n] * S % mod) % mod; s = (s + p[n][n] * S % mod) % mod; if(f < 0)f += mod; if(s < 0)s += mod; cout << f << " " << s << endl; } return 0; }