Khan's Army

Time limit1sMemory limit1024 MB

Summary

Counts the permutations of 1 to N in which the K bodyguard numbers form a longest increasing subsequence.

Level: Medium6 of 10
Topics: Dynamic programming, Bit manipulation, Combinatorics
Solved: No attempts yet

Problem

While preparing for battle, Khan Girey numbered every warrior of his army with natural numbers from 1 to $N$ . The warriors know how to fight but cannot count, so whenever they line up, they stand in an arbitrary order.

A group of one or more warriors standing in the line is called a squad. A squad is correct if the numbers of its warriors, read in the order they stand in the line, form a strictly increasing sequence. Among all correct squads, Khan Girey picks the strike squad, the one with the most warriors. For example, in the line 1 3 2 4, the strike squads are 1 3 4 and 1 2 4, while 1 4 is a correct squad but not a strike squad.

Some warriors are the Khan's personal bodyguards.

Write a program that counts the lines in which the bodyguards form a strike squad.

Input

The first line contains the natural number $N$ , the total number of warriors ( $1 \le N \le 15$ ). The second line contains the natural number $K$ , the number of bodyguards ( $1 \le K \le N$ ). The third line contains $K$ distinct natural numbers not exceeding $N$ , the bodyguards' numbers in increasing order, separated by spaces.

Output

Print one number: the number of different ways to line up all warriors so that the bodyguards form a strike squad in every such line.

Hint

The first sample has five warriors. The strike squad must consist of warriors 1, 3, and 4. These 11 lines satisfy the condition: (1, 3, 2, 5, 4), (1, 3, 5, 2, 4), (1, 3, 5, 4, 2), (1, 5, 3, 2, 4), (1, 5, 3, 4, 2), (2, 1, 3, 5, 4), (2, 1, 5, 3, 4), (2, 5, 1, 3, 4), (5, 1, 3, 2, 4), (5, 1, 3, 4, 2), (5, 2, 1, 3, 4).

Examples3

Example 1
Input
```
5
3
1 3 4
```
Expected output
```
11
```
Example 2
Input
```
3
3
1 2 3
```
Expected output
```
1
```
Example 3
Input
```
1
1
1
```
Expected output
```
1
```