벽돌

번호가 1번부터 $N$번까지 붙은 상자 $N$개가 한 줄로 놓여 있다. 처음에는 모두 비어 있다. 시간 순서대로 $M$개의 사건이 일어나고, 각 사건은 위치 $p$로 주어진다. 벽돌 하나가 $p$번 상자로 떨어진다는 뜻이다.

$p$번 상자가 비어 있으면 벽돌은 그 자리에 놓인다. 이미 차 있으면 $p$번 상자를 포함하는 연속된 점유 구간을 최대로 잡아 $[a, b]$라 하자. 이때 벽돌을 구간의 왼쪽인 $a-1$번 상자에 놓거나 오른쪽인 $b+1$번 상자에 놓을 수 있다. 단 그 상자가 존재할 때만 고를 수 있다. 왼쪽은 $a-1 \ge 1$일 때, 오른쪽은 $b+1 \le N$일 때 고를 수 있다.

상자의 상태를 길이 $N$의 이진 문자열로 적어 보자. 0은 빈 상자, 1은 찬 상자다. 상태가 001110111100인 상황에서 8번 위치에 벽돌이 떨어지면 8번은 구간 $[7, 10]$ 안에 있으므로 6번이나 11번에 놓는다. 구간 $[7, 10]$ 안의 어느 위치에 떨어져도 결과는 같다. 2번 위치에 떨어지면 그 상자가 비어 있으므로 벽돌은 2번에 그대로 놓인다.

$N$, $M$과 시간 순서대로 주어진 사건 $M$개가 있을 때, 벽돌 $M$개를 모두 놓고 난 최종 상태가 몇 가지인지 세어라. 벽돌은 서로 구별하지 않으므로 어느 상자가 찼는지만 따진다. 위 설명대로 이진 문자열로 보면, 만들 수 있는 서로 다른 문자열의 개수를 구하는 문제다. 답을 1000000007로 나눈 나머지를 출력한다.

첫째 줄에 $N$과 $M$이 공백으로 구분되어 주어진다.

둘째 줄에 사건 $M$개의 위치 $p$가 시간 순서대로 공백으로 구분되어 주어진다.

제한:

• $1 \le M \le 100000$
• $M \le N \le 1000000$
• $1 \le p \le N$

만들 수 있는 서로 다른 최종 상태의 개수를 1000000007로 나눈 나머지를 한 줄에 출력한다.