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|