Coco wants to play a tree-building game with chocolates. Each chocolate has an integer between $0$ and $N-1$ written on it. The tree-building game involves creating a binary tree where each node has one chocolate, and it proceeds as follows:

• Initially, create the root of the tree and place a chocolate with any integer on it.
• After that, repeat the following:
  • Select a leaf node. Let $M$ be the number written on the chocolate at that position.
  • Add two child nodes below the selected node, and choose two numbers whose sum is $M$ or $N+M$. Place chocolates with these two numbers on the two child nodes.

Coco has an infinite supply of chocolates with the numbers $a_1, a_2, \cdots, a_k$ written on them, but she does not have chocolates with other numbers and must borrow them from Hanbyeol. Given that she wants to build a tree where the depth of every leaf (the number of edges on the path to the root) is exactly $H$, find the minimum number of chocolates she needs to borrow from Hanbyeol to complete the tree.

Input

The first line contains the values $N$, $H$, and $k$. ($2 \le N \le 500$, $1 \le H \le 60$, $1 \le k \le N$)

The next line contains the values $a_1, a_2, \cdots, a_k$. ($0 \le a_i < N$) The values $a_i$ are distinct.

Output

Output the minimum number of chocolates that must be borrowed from Hanbyeol on a single line.

Examples

Input 1

2 5 1
1

Output 1

21

Input 2

3 5 2
1 2

Output 2

0