You are given a binary number X. Now you are given q queries. In each query you will be given a number a and you have to tell what will be the value of X in decimal number system after calculating modulo $10^9 + 7$ if you flip the first a bits of the number from the left to right direction.

Note : Please go through the sample input output.Also the number before performing each query is the original number X without any changes.

Input
First line contains a number N as input denoting length of the binary number. Next line contains a binary number X as input.
Next line contains a number q as input that denotes total number of queries.
Next q lines contains an integer a each.
Output
Give the output of each query as required in a new line

Constraints
$1 \le |X| \le 10^5$ where $|X| = N$ is the length of binary number
$1 \le q \le 10^5$
$1 \le a \le |X|$