Problem Statement

On yukicoder, yuki learned that, for Kadomatsu sequences, there is something called a Super Rich Kadomatsu sequence.
Having become interested in Fibonacci sequences, yuki similarly came up with something called a Super Fibonacci sequence.

A Super Fibonacci sequence is a sequence generated from its first N terms \(A_1, A_2, ... , A_N\), where the value \(F(k)\) of the k-th term is the sum of the immediately preceding N terms.
Strictly speaking, \(F(k)\) is defined as follows.
- If \(k\le N\), then \(\displaystyle F(k) = A_k \)
- If \(k\gt N\), then \(\displaystyle F(k) = F(k-1) + F(k-2) + ... + F(k-N) = \sum_{1\le i \le N} F(k-i)\)

For a large integer \(K\), yuki wondered what \(F(K)\) and \(\displaystyle S(K) = \sum_{1\le k \le K} F(k)\) would be.
Find the values of \(F(K)\) and \(S(K)\) modulo \(10^9+7\).

Input

\(N\) \(K\)
\(A_1\) \(A_2\) ... \(A_N\)

\(N, K, A_i\) are all integers.
This problem has the following limits depending on the test case.
testcase01～10: \(2 \le N \le 10^4, N \lt K \le 10^6\) (equivalent to difficulty ★★)
testcase11～20: \(2 \le N \le 30, N \lt K \le 10^{12}\) (equivalent to difficulty ★★★)
In all cases, \(0 \le A_i \le 9\) holds.

Hint: Using a single approach for both groups of cases is not necessarily the best choice.

Output

Compute the values of \(F(K)\) and \(S(K)\), and output each of them modulo \(10^9+7\), separated by a space, on one line.

Sample

2 5
1 1

5 12

5 10
1 2 3 4 5

214 438

30 987654321012
3 1 4 1 5 9 2 6 5 3 5 8 9 7 9 3 2 3 8 4 6 2 6 4 3 3 8 3 2 7

923032656 920866414