该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

T2. 铺地砖 (domino)

来源：CSP-J 入门级模拟题 02 — 递推算法

题目描述

小明家装修，要用 $1\times 2$ 的骨牌铺满一块 $2\times N$ 的矩形地面。骨牌可以竖着放（占 $2\times 1$），也可以横着放（占 $1\times 2$，需要两行并排）。

但是，地面上有 $M$ 列因为管道凸起而整列都不能铺骨牌（两个格子都损坏）。

请你帮小明计算：有多少种不同的铺法能将剩余的地面铺满？答案可能很大，请对 $10^9+7$ 取模。

输入格式 domino.in

第一行两个整数 $N, M$。

接下来 $M$ 行，每行一个整数 $c$，表示第 $c$ 列整列损坏（$1\le c\le N$）。保证 $c$ 互不相同。

输出格式 domino.out

一行一个整数，表示方案数模 $10^9+7$。

样例

样例 #1

3 0

3

解释：$2\times 3$ 无损坏：竖竖竖、竖+两横、两横+竖，共3种。

样例 #2

3 1
2

1

解释：第2列损坏，只能第1列竖放+第3列竖放，共1种。

数据范围

对于全部数据，$1\le N\le 10^5$，$0\le M\le \min(2N, 100)$，损坏位置互不相同。