Bitsir

Considerăm numerele naturale $N$, $X$, $Y$, $M_1, M_2, \ldots, M_N$. Șirul de numere naturale $A_1, A_2, \ldots, A_N$ este numit bun dacă următoarele condiții sunt satisfăcute simultan:

• $A_1 \text{ OR } A_2 \text{ OR } \ldots \text{ OR } A_N = X$, unde $\text{ OR }$ reprezintă operația "sau pe biți".
• $A_1 \text{ XOR } A_2 \text{ XOR } \ldots \text{ XOR } A_N = Y$, unde $\text{ XOR }$ reprezintă operația "sau exclusiv pe biți".
• $A_i \text{ AND } M_i = M_i$, pentru $1 \leq i \leq N$, unde $\text{ AND }$ reprezintă operația "și pe biți".

Se dau $N$, $X$, $Y$ și $M_{1}, M_{2}, \ldots, M_{N}$, cu semnificația din enunț.

Cerință

Să se determine dacă există șiruri bune, respectiv să se determine numărul de șiruri bune, modulo $1 \ 000 \ 000 \ 007$.

Date de intrare

Fișierul de intrare bitsir.in conține pe prima linie trei numere naturale $N$, $X$ și $Y$, și pe a doua linie numerele naturale $M_{1}, M_{2}, \ldots, M_{N}$. Numerele aflate pe aceeași linie a fișierului sunt separate prin câte un spațiu.

Date de ieșire

Fișierul de ieșire bitsir.out conține exact două linii. Fișierul conține pe prima linie mesajul DA, dacă există șiruri bune, sau mesajul NU în caz contrar, iar pe a doua linie numărul de șiruri bune determinat. Valoarea de pe a doua linie a fișierului trebuie să fie un număr natural cuprins în intervalul $[0, 1 \ 000 \ 000 \ 006]$.

Restricții și precizări

• $1 \leq N \leq 100 \ 000$;
• $0 \leq X, Y \leq 2^{30}-1$;
• $0 \leq M_i \leq X$;
• Dacă prima linie a fișierului de ieșire este corectă, dar a doua linie a fișierului de ieșire nu este corectă, se acordă $50\%$ din punctajul corespunzător testului respectiv.
• Dacă prima linie a fișierului de ieșire nu este corectă, se acordă $0\%$ din punctajul corespunzător testului respectiv.
• Operația $\text{OR}$ este reprezentată în C/C++ prin |. Spre exemplu, $12 \text{ OR } 10 = 14$.
• Operația $\text{XOR}$ este reprezentată în în C/C++ prin ^. Spre exemplu, $12 \text{ XOR } 10 = 6$.
• Operația $\text{AND}$ este reprezentată în C/C++ prin &. Spre exemplu, $12 \text{ AND } 10 = 8$.

Exemplul 1

bitsir.in

3 11 10
8 2 0

bitsir.out

DA
12

Explicație

Șirurile bune sunt:

• $8, 3, 1$;
• $8, 11, 9$;
• $9, 2, 1$;
• $9, 3, 0$;
• $9, 10, 9$;
• $9, 11, 8$;
• $10, 3, 3$;
• $10, 11, 11$;
• $11, 2, 3$;
• $11, 3, 2$;
• $11, 10, 11$;
• $11, 11, 10$.

Exemplul 2

bitsir.in

3 7 5
2 3 6

bitsir.out

NU
0

Explicație

Nu există șiruri bune.

Exemplul 3

bitsir.in

10 31 24
5 17 1 6 0 30 12 15 8 23

bitsir.out

DA
8388608