Theater Seats

A theater has one row of seats numbered from 1 to N from left to right. Each audience member normally sits in the seat printed on their ticket. A regular audience member may instead move exactly one seat to the left or right. For example, a person with ticket 7 may sit in seat 6, 7, or 8, but not in seat 5 or 9.

Some audience members are VIP members. A VIP member must sit only in the seat with the same number as their ticket and cannot move to an adjacent seat.

Today's performance is sold out, so every seat from 1 through N has been sold. Given the seat numbers of the VIP members, compute how many different valid seating arrangements are possible.

For example, when there are 9 seats and seats 4 and 7 are VIP seats, 123456789 is valid. So are 213465789 and 132465798. However, 312456789 is invalid because one person moves more than one seat away, and 123546789 is invalid because it violates a VIP seat.

The first line contains the number of seats N. N is between 1 and 40, inclusive.

The second line contains the number of VIP seats M. M is between 0 and N, inclusive.

Each of the next M lines contains one VIP seat number. The seat numbers are given in increasing order.

Print the number of seating arrangements that satisfy the conditions. The answer does not exceed 2,000,000,000. (2,000,000,000 < 2^31 - 1)