問題文

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>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<K\le {10}^6$ （難易度★★相当）
testcase11～20: $2\le N\le 30,N<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