考虑一个包含 $N$ 个盒子的区域，初始时所有盒子均为空，编号从 $1$ 到 $N$。我们有 $M$ 个按时间顺序给出的事件。每个事件由一个数字 $p$ 描述：一块砖落在位置 $p$。如果该位置的盒子是空的，砖块必须留在那里。否则，考虑包含位置 $p$ 的连续已占用盒子的完整区间。我们有两个选择：可以将新砖块放在该区间的左侧或右侧（如果存在的话）。区间 $[a, b]$ 的左侧是位置 $a - 1$，右侧是位置 $b + 1$。

说明

给定一个长度为 $N$ 的二进制字符串，其中 $0$ 表示空盒子，$1$ 表示已占用盒子：$001110111100$。如果砖块落在位置 $8$（或区间 $[7, 10]$ 内的任何其他位置），我们可以将这块新砖放在位置 $6$ 或位置 $11$。如果它落在位置 $2$（该位置为空），则砖块必须留在那里。

任务

给定 $N$、$M$ 以及 $M$ 个事件（按时间顺序），确定放置 $M$ 块砖后，$N$ 个位置（盒子）可能形成的本质不同的配置数量。答案需对 $1.000.000.007$ 取模。砖块是无序的，因此它们的顺序无关紧要。如果考虑二进制解释（如说明中所述），你需要求出可以形成的本质不同的二进制字符串的数量。

数据范围

• $1 \le M \le 100.000$
• $1 \le M \le N \le 1.000.000$
• $1 \le p \le N$

输入格式

• 第一行：$N, M$
• 第二行：$M$ 个数字，表示 $M$ 个事件（$p$ 的值）

输出格式

• 一个数字，表示可以获得的本质不同的配置数量，对 $1.000.000.007$ 取模。

样例

样例输入 1

5 4
2 2 4 4

样例输出 1

3