#include using namespace std; typedef long long ll; const ll mod = 1e9 + 7; typedef vector vec; typedef vector mat; mat mat_mul(mat &A, mat &B) { mat res(A.size(), vec(B[0].size())); for (int i = 0; i < A.size(); i++) { for (int k = 0; k < B.size(); k++) { for (int j = 0; j < B[0].size(); j++) { res[i][j] = (res[i][j] + A[i][k] * B[k][j]) % mod; } } } return res; } mat mat_id(int n) { mat res(n, vec(n)); for (int i = 0; i < n; i++) { res[i][i] = 1; } return res; } mat mat_pow(mat A, ll n) { mat res = mat_id(A.size()); while (n > 0) { if (n & 1) res = mat_mul(res, A); A = mat_mul(A, A); n >>= 1; } return res; } mat companion(vector cf) { int n = cf.size(); mat res(n + 1, vec(n + 1)); for (int i = 0; i < n; i++) { res[n - 1][i] = cf[n - i - 1]; } for (int i = 0; i < n - 1; i++) { res[i][i + 1] = 1; } res[n][1] = 1; res[n][n] = 1; return res; } ll N, K; vector iv; ll fib[1000000]; void solve1() { vector cf; for (int i = 0; i < N; i++) { cf.push_back(1); } mat cp = companion(cf); cp = mat_pow(cp, K - 1); ll ans = 0; ll sum = 0; iv.push_back(iv[0]); for (int i = 0; i <= N; i++) { ans += cp[0][i] * iv[i]; sum += cp[N][i] * iv[i]; ans %= mod; sum %= mod; } cout << ans << " " << sum << endl; } void solve2() { ll ans = 0; ll sum = 0; for (int i = 0; i < N; i++) { fib[i] = iv[i]; sum += iv[i]; } sum %= mod; ll temp = sum; for (int i = N; i < K; i++) { fib[i] = temp; temp += fib[i]; temp -= fib[i - N]; temp %= mod; if (temp < 0) temp += mod; sum += fib[i]; sum %= mod; } cout << fib[K - 1] << " " << sum << endl; } int main() { cin >> N >> K; for (int i = 0; i < N; i++) { ll a; cin >> a; iv.push_back(a); } if (N <= 30) { solve1(); } else { solve2(); } }