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