tl3 | bun

Un șir se numește bun dacă suma elementelor este egală cu numărul elementelor. Mai exact, un șir
$x_1, x_2, \dots, x_k$ se numește bun dacă $x_1 + x_2 + x_3 + \ldots + x_k = k$.
Subsecvența $\lbrack l \dots r \rbrack$ a unui șir $x_1, x_2, \dots x_k$ este șirul format din valorile $x_l, x_{l+1}, x_{l+2}, . . . , x_r$ în această ordine.

Cerință

Se dă $C$, $N$ și un șir $a_1, a_2, \dots, a_N$ de $N$ numere naturale. Răspunde la următoarele 3 cerințe:

1. Dacă $C=1$, trebuie să afișezi DA dacă șirul $a$ este bun și NU altfel.
2. Dacă $C=2$, trebuie să afișezi un șir $b_1, b_2, \dots, b_N$ cu proprietatea că numărul de subsecvențe bune din $b$ este cât de mare posibil. (Observați că șirul $a$ nu are nicio legătură cu această cerință)
3. Dacă $C=3$, trebuie să afișezi numărul de subsecvențe bune ale șirului $a$.

Date de intrare

Pe prima linie a fișierului de intrare bun.in se află numărul $C$. Pe a doua linie se află numărul $N$. Pe a treia linie se află șirul $a_1, a_2, \dots, a_N$.

Date de ieșire

Să se afișeze pe prima linie din fișierul bun.out răspunsul la cerința corespunzătoare.

Restricții și precizări

• $C \in \lbrace 1,2,3 \rbrace$
• $2 \leq N \leq 100 \ 000$
• $0 \leq a_i \leq 3$ (!!!)

Exemplul 1

bun.in

1
6
0 1 2 0 3 0

bun.out

DA

Explicație

În primul exemplu, avem $0 + 1 + 2 + 0 + 3 + 0 = 6$, deci șirul este bun.

Exemplul 2

bun.in

1
2
0 1

bun.out

NU

Explicație

În al doilea exemplu, avem $0 + 1 = 1 \neq 2$, deci șirul nu este bun.

Exemplul 3

bun.in

2
2
2 3

bun.out

1 1

Explicație

În al treilea exemplu, putem forma șirul $\lbrace 1, 1 \rbrace$ care are 3 subsecvențe bune.

Exemplul 4

bun.in

3
8
1 1 2 0 0 0 1 3

bun.out

11

Explicație

În ultimul exemplu, avem 11 subsecvențe bune. Acestea sunt $\lbrace (1, 1)$; $(1, 2)$; $(1, 4)$; $(1, 8)$; $(2, 2)$; $(2, 4)$; $(2, 8)$; $(3, 4)$; $(3, 8)$; $(5, 8)$; $(7, 7) \rbrace$