TopCoder

User's AC Ratio

72.7% (8/11)

Submission's AC Ratio

17.1% (13/76)

Tags

Description

應該聽過費氏數列吧?

費氏數列是一個滿足$F_n=F_{n-1}+F_{n-2}$且$F_1=1,F_2=1$的一個數列,或是可以寫成$F_n=\frac{\phi ^ n-\psi ^ n}{\phi -\psi}$,其中$\phi=\frac{1+\sqrt{5}}{2},\psi=\frac{1-\sqrt{5}}{2}$。

相傳在費波那契,也就是提出上述費氏數列的人,老年的時候,發現了一種新的數列,姑且稱為$f$好了,而他之前提出的數列只是$f$的一種特例而已。

那什麼是$f$呢?就是滿足通式$f_n={k_1}f_{n-1}+{k_2}f_{n-2}+\ldots+{k_m}f_{n-m}=\sum\limits_{i=1}^ m{k_if_{n-i}}$,且$f_1=f_2=\ldots=f_m=1$之數列,不難發現,我們耳熟能詳的費氏數列只是$m=2,k_1=1,k_2=1$的一個特例而已。

你的任務是設計一個程式,計算給定$m$以及$k_1,k_2,\ldots,k_m$時之$f$數列的第$n$項。

Input Format

輸入包含一個正整數$n,m$。
接著有$m$個整數$k_1,k_2,\ldots,k_m$。

Output Format

輸出滿足給定條件之$f_n$,由於結果可能很大,你只要輸出答案除$1000000007$的餘數就好了。

Sample Input

4 3
1 2 3

Sample Output

6

Hints

For $5\%$ of the testdata: $n\le 8,m\le 3$
For $70\%$ of the testdata: $n\le 10^ 8, m\le 50$
For $100\%$ of the testdata: $n\le 10^ {18}, m\le 100$
For $100\%$ of the testdata: $\forall 1\le i\le m,k_i\le 1000$

Problem Source

Set by waynetu

Subtasks

For Testdata: 0 ~ 3, Score: 70
For Testdata: 4 ~ 15, Score: 30
For Testdata: 16 ~ 16, Score: 0
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 1000 65536 65536
1 1000 65536 65536
2 1000 65536 65536
3 1000 65536 65536
4 10000 131072 65536
5 10000 131072 65536
6 10000 131072 65536
7 10000 131072 65536
8 1000 65536 65536
9 1000 65536 65536
10 1000 65536 65536
11 1000 65536 65536
12 1000 65536 65536
13 1000 65536 65536
14 1000 65536 65536
15 1000 65536 65536
16 3000 262144 65536