M - お絵かき Editorial /

Time Limit: 10 sec / Memory Limit: 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
10 個のマスのうち 1 個または 2 個が黒い絵が全て描ける。

Sample Input 2

1000000000 4
2015
2015
123456789
27

Sample Output 2

782767239