#define _USE_MATH_DEFINES #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair i_i; typedef pair ll_i; typedef pair d_i; typedef pair ll_ll; typedef pair d_d; struct edge { int u, v; ll w; }; int INF = INT_MAX / 10; ll MOD = 1000000007; ll _MOD = 1000000009; double EPS = 1e-10; vector< vector > matmul(vector< vector >& A, vector< vector >& B) { int n = A.size(); vector< vector > C(n, vector(n)); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) for (int k = 0; k < n; k++) C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % MOD; return C; } vector< vector > matpow(vector< vector > A, ll x) { int n = A.size(); vector< vector > B(n, vector(n)); for (int i = 0; i < n; i++) B[i][i] = 1; while (x > 0) { if (x % 2) B = matmul(B, A); x /= 2; A = matmul(A, A); } return B; } int main() { int N; ll K; cin >> N >> K; vector A(N); for (int i = 0; i < N; i++) cin >> A[i]; if (N <= 30) { vector > a(N * 2, vector(N * 2)); for (int i = 0; i < N; i++) a[0][i] = a[N + i][i] = a[N + i][N + i] = 1; for (int i = 0; i + 1 < N; i++) a[i + 1][i] = 1; vector > b = matpow(a, K - 1); int f = 0, s = 0; for (int i = 0; i < N; i++) { f = (f + b[N - 1][i] * A[N - i - 1]) % MOD; s = (s + b[N * 2 - 1][i] * A[N - i - 1]) % MOD; } cout << f << ' ' << (f + s) % MOD << endl; } else { vector a(K); ll sum = 0, s = 0; for (int i = 0; i < N; i++) { a[i] = A[i]; sum = (sum + A[i]) % MOD; } for (int i = N; i < K; i++) { a[i] = sum; sum = (sum + a[i] - a[i - N]) % MOD; } for (int i = 0; i < K; i++) s = (s + a[i]) % MOD; cout << a[K - 1] << ' ' << s << endl; } }