M - お絵かき
解説
/
入力は以下の形式で標準入力から与えられる。
答えを一行に出力せよ。
10 個のマスのうち 1 個または 2 個が黒い絵が全て描ける。
実行時間制限: 10 sec / メモリ制限: 256 MB
Problem Statement
すぬけ君は、絵を描くことにした。 最初に、すぬけ君は細長い白い紙を用意し、1 \times N のマス目に区切った。 次に、すぬけ君は、K 回の操作を行う。 i 回目の操作では、連続する a_i このマス目を選び、全て黒く塗る。 この操作では、選ばれたマス目のうち白かったものは黒に変わり、もともと黒かったマスはそのままである。
すぬけ君が何通りの絵をかくことができるか、\rm{mod}\ 1,000,000,007 で求めよ。 二つの絵はあるマス目の最終的な色が異なるときに異なる絵であるとみなす。 回転して同じになる絵でも異なるものとみなす。
Constraints
- 1 \leq N \leq 10^9
- 1 \leq K \leq 4
- 1 \leq a_i \leq N
Input Format
N K a_1 : a_K
Output Format
Sample Input 1
10 2 1 1
Sample Output 1
55
Sample Input 2
1000000000 4 2015 2015 123456789 27
Sample Output 2
782767239