Someone provides you a binary number N and asked you to process the Q queries. In each query, you have been given a number K and want you to flip the first K bits of the number from left to right.

Input

First-line contains a number X as input denoting the length of the binary number. The next line contains a binary number N as input.
The next line contains a number Q as input that denotes a total number of queries.
Next, Q lines contain an integer K each.

Output

In each query, print the decimal representation of X mod 10⁹+ 7 after the flip.

Constraints

1 ≤ |N| ≤ 10⁵ where |N|=X is the length of a binary number
1 ≤ Q ≤ 10⁵
1 ≤ K ≤ |N|