# Angry Xiao N

https://www.luogu.com.cn/problem/P7468

There is a game with infinite levels, starting from level 0. Some are normal levels while some are special levels.

Completing normal levels doesn't give you points while completing special level $x$ gives you $a_0 + a_1x + a_2x^2 + a_3x^3 ... a_{k-1}x^{k-1}$ points. The values of $a_0$ to $a_{k-1}$ are given

The sequence of levels is given as follows:
1. Let string $s$ be 'a'
1. Let $t$ be $s$, but where all 'a' are replaced by 'b' and all 'b' replaced by 'a'
1. Append $t$ to $s$
1. Repeat step $2$ and $3$ infinitely many times
1. The $i$-th level is normal if $s[i]$ is ‘a’ and special if $s[i]$ is ‘b’

Based on the above rules, the first few characters of $s$ are abbabaabbaababba...

You have to find the total number of points you can get by completing the first $n$ levels, mod $1000000007$.

## Constraints

$n$ is given in binary. $n$ has at most $500000$ binary digits
$k \leq 500$
$0 \leq a_i \leq 10^9$

## Input

The first line contains a single integer, $n$. $n$ is given in binary.
The next line is $k$
The next line contains $k$ integers, which is $a_0$ to $a_{k-1}$
Output

Output the total number of points you can get by completing the first $n$ levels, mod $1000000007$.

## Sample

Input 1

1000
3
3 2 1

Output 1
`110`

Input 2

11111100101
4
2 0 2 1

Output 2
`143901603`

Input 3

1001011001101001
16
1 0 0 1 0 1 1 0 0 1 1 0 1 0 0 1

Output 3
`184740992`

For sample 1:

$n = 8$
$1,2,4,7$ are special levels while $0,3,5,6$, are normal levels.
$(3 + 2\times1 + 1\times1\times1) + (3 + 2\times2 + 1\times2\times2) + (3 + 2\times4 + 1\times4\times4) + (3 + 2\times7 + 1\times7\times7) = 110$