Traces of Binary Search

Geon-i and Junseong play a game with a sorted array $A = [a_1, a_2, \cdots, a_N]$ of length $N$. Junseong picks one element of the array at random. The answer range is the range of indices where the element Junseong picked could be, and it starts as $[1, N]$.

Geon-i can pick an element in the current answer range and ask whether the number he is thinking of is that element. Junseong answers with one of Yes, Up, or Down. Junseong does not lie, and the game ends when Junseong answers Yes. The sequence $[t_1, t_2, \cdots, t_K]$ of the $K$ elements Geon-i asked, in order, is called the trace of binary search.

Geon-i always makes the best choice in every game, so when the answer range is $[s, e]$, he always asks about $a_{s + \left\lfloor \frac{e-s}{2} \right\rfloor}$.

• If Junseong answers Up, the next range is $[s + \left\lfloor \frac{e-s}{2} \right\rfloor + 1, e]$.
• If Junseong answers Down, the next range is $[s, s + \left\lfloor \frac{e-s}{2} \right\rfloor - 1]$.

Given a trace of binary search, print the number of arrays $A$ that could produce it.

The first line contains the size $N$ of the array and the size $K$ of the trace, separated by a space.

The second line contains the integers $t_1, t_2, \cdots, t_K$ that make up the trace, separated by spaces.

Print the number of possible arrays $A$, modulo $10^9 + 7$.

• $1 \le N \le 100$
• $1 \le K \le \lfloor \log_2{N} \rfloor + 1$
• $1 \le a_1 < a_2 < \cdots < a_N \le 100$
• $1 \le t_i \le 100$
• For all $i \neq j$, $t_i \neq t_j$
• $1 \le i, j \le K$
• Only traces for which at least one possible array $A$ exists are given as input.