32179번 - 이분탐색의 흔적

문제

건이와 준성이는 오름차순으로 정렬된 길이가 $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$로 가능한 배열의 개수를 1ドル,000円,000円,007円(= 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$가 1ドル$개 이상 존재하는 흔적만이 입력으로 주어진다.

노트