#include #include #include #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 > operator * (vector > const & p, vector > const & q) { int n = p.size(); vector > r(n, vector(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 operator * (vector > const & p, vector const & q) { int n = p.size(); vector 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 a(n); repeat (i,n) cin >> a[i]; if (n <= 30) { vector > fe(n, vector(n)); repeat (i,n) fe[0][i] = 1; repeat (i,n-1) fe[i+1][i] = 1; vector > se(n+1, vector(n+1)); se[0][0] = 2; se[0][n] = mod - 1; repeat (i,n) se[i+1][i] = 1; vector > f(n, vector(n)); repeat (i,n) f[i][i] = 1; vector > s(n+1, vector(n+1)); repeat (i,n+1) s[i][i] = 1; for (int i = 0; (1ll< x = a; vector 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 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; }