이분탐색의 흔적

건이와 준성이는 오름차순으로 정렬된 길이가 $N$인 배열 $A = [a_1, a_2, \cdots, a_N]$를 보며 게임을 한다. 준성이는 배열의 원소 중 무작위로 하나를 선택한다. 답 구간은 준성이가 선택한 원소가 존재할 수 있는 인덱스의 구간을 의미하며, 처음에는 $[1, N]$으로 시작한다.

건이는 준성이에게 가능한 답 구간의 원소를 하나 골라, 생각한 숫자가 그 원소가 맞는지 질문할 수 있다. 준성이는 그에 따라 Yes, Up, Down 중 하나를 답한다. 준성이는 거짓말을 하지 않으며, Yes를 답하면 게임이 종료된다. 이때 건이가 부른 $K$개 원소를 순서대로 나열한 배열 $[t_1, t_2, \cdots, t_K]$를 이분탐색의 흔적이라 한다.

건이는 모든 게임에서 항상 최선의 선택을 하므로, 가능한 답 구간이 $[s, e]$일 때 항상 $a_{s + \left\lfloor \frac{e-s}{2} \right\rfloor}$를 물어본다.

• 준성이가 Up을 답하면 다음 구간은 $[s + \left\lfloor \frac{e-s}{2} \right\rfloor + 1, e]$이 된다.
• 준성이가 Down을 답하면 다음 구간은 $[s, s + \left\lfloor \frac{e-s}{2} \right\rfloor - 1]$이 된다.

이분탐색의 흔적이 주어졌을 때, 그 흔적을 만들 수 있는 배열 $A$의 개수를 구하여라.

첫 번째 줄에 배열의 크기 $N$과 이분탐색의 흔적의 크기 $K$가 공백으로 구분되어 주어진다.

두 번째 줄에 이분탐색의 흔적을 이루는 정수 $t_1, t_2, \cdots, t_K$가 공백으로 구분되어 주어진다.

배열 $A$의 개수를 $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$
• 모든 $i \neq j$에 대해 $t_i \neq t_j$
• $1 \le i, j \le K$
• 가능한 배열 $A$가 하나 이상 존재하는 흔적만 입력으로 주어진다.