Uolevi has a perfect binary tree of size $n = 2^{k} - 1$. He wants you to answer $q$ queries of the following form: Given the index of a node in the inorder traversal of the tree, what is the index of the node in the breadth-first traversal of the tree?

Since the amount of output could be very large, output the sum of all answers to queries mod $10^{9} + 7$.

In inorder traversal, first all left children appear (in inorder), then the node appears, then all right children appear (in inorder).

Here is the inorder indexing of a perfect binary tree of size 7:

In breadth-first traversal, a node $a$ appears before another node $b$ if $depth(a) < depth(b)$ or $depth(a) = depth(b)$ and there is some node where $a$ appears in the node's left subtree, and $b$ appears in the node's right subtree.

Breadth-first indexing of the same tree:

Both traversals start from the root of the tree, and are 1-indexed.

Input

The first line of input contains two integers $k$ and $q$: Uolevi's tree has size $2^k - 1$, and there are $q$ queries.

The second line contains the $q$ queries, each a value $t_{i}$: What is the index of the node, whose index in the inorder traversal of the tree is $t_{i}$, in the breadth-first traversal of the tree?

Output

Output a single integer: The sum of the answers to all queries mod $10^{9} + 7$. The answer to each query is the index of the node in the tree's breadth-first traversal.

Constraints

• $1 \leq k \leq 60$
• $1 \leq q \leq 10^{6}$
• $1 \leq t_{i} \leq n$

Example

Input:

3 7
1 2 3 4 5 6 7

Output:

28

Explanation:
The answers to the queries are:

4 2 5 1 6 3 7