ND

Cerință

Fie $D$ și $M$ două numere naturale. Fie $N_1, N_2, \dots, N_D$ numere naturale astfel încât $\forall 1 \leq i \leq D, 1 \leq N_i \leq M$. Fie un grid $D$ dimensional. Fiecare punct $(x_1, x_2, \dots, x_D)$ pentru care $0 \leq x_i \leq N_i, \forall 1 \leq i \leq D$ are asociată o valoare binară, inițial $0$.

Într-o operație putem alege $D$ numere, $a_1, a_2, \dots, a_D$ astfel încât $\forall 1 \leq i \leq D$ să avem $0 \leq a_i \leq N_i$. Valoarea tuturor punctelor $(x_1, x_2, \dots, x_D)$ care respectă $\forall 1 \leq i \leq D, 0 \leq x_i \leq a_i$ se inversează (din $0$ în $1$ și din $1$ în $0$).

Fie $f : \{ 0, 1, 2, \dots, M \} \rightarrow \{ 0, 1 \}$ o funcție oarecare. Se dorește ca în final configurația valorilor să respecte următoarea condiție:

Valoarea asociată unui punct $(x_1, x_2, \dots, x_D)$ să fie $\left( \sum_{i=1}^D { f(x_i) } \right) \% 2$. Mai exact dacă un număr impar de $f(x_i)$ sunt $1$, atunci valoarea asociată punctului trebuie să fie $1$. Altfel aceasta trebuie să fie $0$.

Se cere numărul minim de operații necesare pentru a obține configurația dorită. Deoarece acest număr poate fi foarte mare se cere afișarea modulo $10^8+7$.

Date de intrare

Pe prima linie se află $D$ și $M$, numărul de dimensiuni și limita numerelor $N_i$. Pe a doua linie se află $D$ numere, $N_1, N_2, \dots, N_D$, separate prin spații. Pe a treia linie se află șirul de valori pentru funcția $f$ (corespunzătoare indicilor $0 \dots M$), neseparate prin spațiu.

Date de ieșire

Să se afișeze numărul minim de operații necesare pentru a obține configurația.

Restricții și precizări

• $1 \leq D \leq 10^5$
• $1 \leq M \leq 10^6$
• $1 \leq N_i \leq M, \forall 1 \leq i \leq D$

Exemplul 1

stdin

1 5
5
011010

stdout

4

Exemplul 2

stdin

3 6
4 6 1
0101010

stdout

12