un ultim efort #1 | Bob

Dezamăgiți de lipsa fotbalului din ultima perioadă, Ștefan și Georgian și-au deschis (în secret) o afacere cu boabe de cafea, comercializând $K$ tipuri diferite de cafea. Astfel, timp de $N$ zile ei produc cafea, urmând să formeze din boabele obținute în zile consecutive pachete ce conțin toate tipurile de cafea.

Concret, cei doi știu pentru fiecare zi ce tipuri de cafea produc în acea zi (posibil niciun tip, caz în care afacerea ia o pauză), după care ei împart zilele în secvențe continue astfel încât, pentru fiecare tip de cafea, fiecare secvență de zile să conțină cel puțin o zi în care să fie produs acel tip de cafea.

Cerință

Înainte de a se apuca de împachetat boabele, Ștefan și Georgian își pun două întrebări:

1. Care este numărul maxim de pachete ce pot fi formate?
2. Care este numărul de moduri de a împărți zilele astfel încât să se formeze număr maxim de pachete valide (ce conțin toate tipurile de cafea)?

Date de intrare

Pe prima linie se găsește un număr întreg $P$, reprezentând numărul cerinței de rezolvat.
Pe cea de-a doua linie se găsește un număr întreg $T$, reprezentând numărul de scenarii pentru care va trebui să rezolvați problema.
Urmează cele $T$ instanțe ale problemei, fiecare fiind compusă din $N + 1$ linii: pe prima linie se vor afla două numere întregi $N$ și $K$, reprezentând numărul de zile, respectiv numărul de tipuri diferite de cafea; pe următoarele $N$ linii câte $K$ cifre binare, cea de-a $j$-a cifră de pe linia $i$ fiind $0$ dacă în ziua $i$ tipul $j$ de cafea nu este produs, sau fiind $1$ dacă în ziua $i$ tipul $j$ de cafea este produs.

Date de ieșire

Pentru fiecare dintre cele $T$ instanțe se va afișa răspunsul, începând de la o linie noua, după cum urmează:

1. Dacă $P = 1$, atunci se va afișa pe o singură linie numărul maxim de pachete valide ce pot fi formate.
2. Dacă $P = 2$, atunci se va afișa pe o singură linie numărul de moduri de a împărți zilele în secvențe continue astfel încât să se formeze număr maxim de pachete. Răspunsul va fi afișat $\text{mod } 1\ 000\ 000\ 007$.

Restricții și precizări

• $1 ≤ P ≤ 2$
• $1 ≤ T ≤ 3$
• $1 ≤ N ≤ 200\ 000$
• $1 ≤ K ≤ 20$
• Se garantează că fiecare tip de cafea apare în cel puțin una dintre cele $N$ zile.

Punctare

• Pentru 6 puncte: $P = 1, N ≤ 15$
• Pentru alte 6 puncte: $P = 1, N ≤ 100$
• Pentru alte 9 puncte: $P = 1, N ≤ 2\ 000$
• Pentru alte 10 puncte: $P = 1, N ≤ 200\ 000$
• Pentru alte 10 puncte: $P = 2, K = 1, N ≤ 200\ 000$
• Pentru alte 4 puncte: $P = 2, N ≤ 15$
• Pentru alte 4 puncte: $P = 2, N ≤ 20$
• Pentru alte 9 puncte: $P = 2, N ≤ 100$
• Pentru alte 8 puncte: $P = 2, N ≤ 700$
• Pentru alte 8 puncte: $P = 2, N ≤ 2\ 000$
• Pentru alte 8 puncte: $P = 2, N ≤ 10\ 000$
• Pentru alte 9 puncte: $P = 2, N ≤ 70\ 000$
• Pentru alte 9 puncte: $P = 2, N ≤ 200\ 000$

Exemplul 1

stdin

1
3
3 3
010
101
111
6 2
10
01
00
10
11
01
5 4
0100
1010
0000
1110
0001

stdout

2
2
1

Exemplul 2

stdin

2
3
3 3
010
101
111
6 2
10
01
00
10
11
01
5 4
0100
1010
0000
1110
0001

stdout

1
3
1

Explicație

Tipurile de cafea produse în fiecare zi sunt:

• În prima zi se va produce doar tipul $2$ de cafea
• În cea de-a doua zi se vor produce tipurile $1$ și $3$ de cafea
• În ultima zi se vor produce toate cele $3$ tipuri de cafea

Numărul maxim de pachete este $2$, și este obținut în mod unic, grupând zilele în următorul fel: $[1, 2], [3]$.

În cel de-al doilea exemplu, numărul maxim de pachete este $2$, fiind obținut în urmatoarele $3$ moduri:

• $[1, 2], [3, 4, 5, 6]$
• $[1, 2, 3], [4, 5, 6]$
• $[1, 2, 3, 4], [5, 6]$

În cel de-al treilea exemplu, numărul maxim de pachete este $1$, fiind obținut prin gruparea tuturor zilelor într-o singură secvență: $[1, 2, 3, 4, 5]$.