package no194; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.InputMismatchException; import java.util.NoSuchElementException; public class Main { static IO io = new IO(); public static long MOD = 1000000007; public static void main(String[] args) { int n = io.nextInt(); long k = io.nextLong(); int[] a = new int[n+1]; for(int i=1;i<=n;i++) { a[i] = io.nextInt(); } if (false && k <= 1000000) { solve1(n,(int) k,a); }else{ solve2(n,k,a); } } public static void solve1(int n,int k,int[] a) { long[] f = new long[k+1]; long sum = 0; long psum = 0; for(int i=1;i<=n;i++) { f[i] = a[i]; psum += a[i]; sum += a[i]; } for(int i=n+1;i<=k;i++) { f[i] = psum; sum = (sum + f[i]) % MOD; psum = (psum - f[i-n] + f[i] + MOD) % MOD; } System.out.println(f[k] + " " + sum); } public static void solve2(int n,long k,int[] a) { MatrixMod m = new MatrixMod(n+1,n+1); for(int i=0;i0) { if (n%2==1) { X.multiplyRightToThis(M); } n/=2; if (n>0) { M.multiplyRightToThis(M); } } return X; } public MatrixMod addToThis(MatrixMod B) { set(add(this,B)); return this; } public MatrixMod multiplyThis(long c) { set(multiply(this, c)); return this; } public MatrixMod multiplyRightToThis(MatrixMod B) { set(multiply(this,B)); return this; } public MatrixMod powThis(long n) { set(pow(this, n)); return this; } public MatrixMod clone() { MatrixMod A = new MatrixMod(rows(), columns()); for(int i=0;i Integer.MAX_VALUE) { throw new NumberFormatException(); } return (int) nl; } public char nextChar() { if (!hasNext()) { throw new NoSuchElementException(); } return (char) readByte(); } public double nextDouble() { return Double.parseDouble(next());} public int[] nextIntArray(int n) { int[] a = new int[n]; for(int i=0;i