#include <iostream> #include <vector> #include <algorithm> #define repeat(i,n) for (int i = 0; (i) < (n); ++(i)) #define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i)) typedef long long ll; using namespace std; const ll mod = 1e9+7; vector<vector<ll> > operator * (vector<vector<ll> > const & p, vector<vector<ll> > const & q) { int n = p.size(); vector<vector<ll> > r(n, vector<ll>(n)); repeat (y,n) { repeat (z,n) { repeat (x,n) { r[y][x] += p[y][z] * q[z][x] % mod; r[y][x] %= mod; } } } return r; } vector<ll> operator * (vector<vector<ll> > const & p, vector<ll> const & q) { int n = p.size(); vector<ll> r(n); repeat (y,n) { repeat (z,n) { r[y] += p[y][z] * q[z] % mod; r[y] %= mod; } } return r; } int main() { int n; ll k; cin >> n >> k; -- k; vector<ll> a(n); repeat (i,n) cin >> a[i]; if (n <= 30) { vector<vector<ll> > fe(n, vector<ll>(n)); repeat (i,n) fe[0][i] = 1; repeat (i,n-1) fe[i+1][i] = 1; vector<vector<ll> > se(n+1, vector<ll>(n+1)); se[0][0] = 2; se[0][n] = mod - 1; repeat (i,n) se[i+1][i] = 1; vector<vector<ll> > f(n, vector<ll>(n)); repeat (i,n) f[i][i] = 1; vector<vector<ll> > s(n+1, vector<ll>(n+1)); repeat (i,n+1) s[i][i] = 1; for (int i = 0; (1ll<<i) <= k; ++ i) { if (k&(1ll<<i)) { f = f * fe; s = s * se; } fe = fe * fe; se = se * se; } vector<ll> x = a; vector<ll> y(n+1); y[0] = a[0]; repeat (i,n-1) y[i+1] = y[i] + a[i+1]; y[n] = 2*y[n-1]; reverse(x.begin(), x.end()); reverse(y.begin(), y.end()); cout << (f * x)[n-1] << ' ' << (s * y)[n] << endl; } else if (k <= 1e6) { vector<ll> f(k+1); repeat (i,n) f[i] = a[i]; ll acc = accumulate(a.begin(), a.end(), 0ll); ll sk = acc; repeat_from (i,n,k+1) { f[i] = acc; sk = (sk + f[i]) % mod; acc = (acc + f[i] - f[i-n] + mod) % mod; } cout << f[k] << ' ' << sk << endl; } return 0; }