問題文

yuki君はyukicoderで門松列に対しスーパーリッチ門松列というものがあることを学んだ。
フィボナッチ数列に興味を持ったyuki君は、同様にスーパーフィボナッチ数列というものを考えてみた。

スーパーフィボナッチ数列は、最初のN項\(A_1, A_2, ... , A_N\)から生成される数列であり、第k項の値\(F(k)\)は、直前のN項の和となる。
厳密に書くと、\(F(k)\)は以下のように定義される。
- \(k\le N\)ならば \(\displaystyle F(k) = A_k \)
- \(k\gt N\)ならば \(\displaystyle F(k) = F(k-1) + F(k-2) + ... + F(k-N) = \sum_{1\le i \le N} F(k-i)\)

yuki君は大きな整数\(K\)に対し、\(F(K)\)及び\(\displaystyle S(K) = \sum_{1\le k \le K} F(k)\)がどうなるか気になった。
\(F(K)\)および\(S(K)\)の値の\(10^9+7\)の剰余を答えよ。

入力

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

\(N, K, A_i\)はいずれも整数である。
本問題はテストケースごとに以下の制限がある。
testcase01～10: \(2 \le N \le 10^4, N \lt K \le 10^6\) （難易度★★相当）
testcase11～20: \(2 \le N \le 30, N \lt K \le 10^{12}\) （難易度★★★相当）
いずれのケースも、\(0 \le A_i \le 9\)は共通である。

ヒント：両ケース群に対し、１つのアプローチで挑むのが良いとは限らない。

出力

\(F(K)\)および\(S(K)\)の値を求め、それぞれ\(10^9+7\)の剰余を取った値を空白区切りで１行で答えよ。

サンプル

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