AT_nyc2015_13 お絵かき

[problemUrl]: https://atcoder.jp/contests/NYC2015/tasks/nyc2015_13 入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ a_1 $ : $ a_K $ 答えを一行に出力せよ。 ``` 10 2 1 1 ``` ``` 55 ``` ``` 1000000000 4 2015 2015 123456789 27 ``` ``` 782767239 ```

N/A

N/A

### Constraints すぬけ君は、絵を描くことにした。 最初に、すぬけ君は細長い白い紙を用意し、$ 1\ \times\ N $ のマス目に区切った。 次に、すぬけ君は、$ K $ 回の操作を行う。 $ i $ 回目の操作では、連続する $ a_i $ このマス目を選び、全て黒く塗る。 この操作では、選ばれたマス目のうち白かったものは黒に変わり、もともと黒かったマスはそのままである。 すぬけ君が何通りの絵をかくことができるか、$ \rm{mod}\ 1,000,000,007 $ で求めよ。 二つの絵はあるマス目の最終的な色が異なるときに異なる絵であるとみなす。 回転して同じになる絵でも異なるものとみなす。 - - - - - - - $ 1\ \leq\ N\ \leq\ 10^9 $ - $ 1\ \leq\ K\ \leq\ 4 $ - $ 1\ \leq\ a_i\ \leq\ N $