Fişierul intrare/ieşire:	permbit.in, permbit.out	Sursă	Algoritmiada 2018 Runda PreONI
Autor	Eugenie Daniel Posdarascu	Adăugată de	Popa Andrei •andreiiii
Timp execuţie pe test	0.5 sec	Limită de memorie	262144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Permbit

Se dau N şiruri a câte M elemente binare, al i-lea şir fiind notat S_i. Fie mulţimea permutărilor P care au proprietatea că, aplicate oricarui şir din cele date, se obţine urmatorul şir. Mai exact, permutarea P este validă dacă:

Se cere să se afişeze:
a) O permutare P oarecare validă
b) Permutarea mediană P (sortând lexicografic toate permutările corecte, se consideră cea care se află la mijloc, în caz că sunt două permutări la mijloc, se considera cea mai mică lexicografic)
c) Numarul de permutări P valide modulo 10⁹ + 7.
Se garantează că există cel puţin o permutare care respectă proprietatea de mai sus.

Date de intrare

Fişierul de intrare permbit.in conţine pe prima linie numărul C, reprezentând cerinţa pe testul respectiv: 1 pentru cerinţa a), 2 pentru cerinţa b) şi 3 pentru cerinţa c).
Pe următoarea linie se află numerele N şi M, iar pe următoarele N linii câte un şir de M biţi.

Date de ieşire

În fişierul de ieşire permbit.out se afla, daca C = 3, numărul de permutări corecte modulo 1.000.000.007, iar dacă nu, o permutare, după caz, oarecare sau mediană.

Restricţii

• 2 ≤ N, M, N * M ≤ 10⁶
• 10 puncte: N, M ≤ 8, 1 ≤ C ≤ 3
• 10 puncte: N, M ≤ 300, C = 1
• 10 puncte: N, M ≤ 300, C = 2
• 10 puncte: N, M ≤ 300, C = 3
• 30 puncte: N * M ≤ 10⁶, C = 2
• 10 de puncte: N * M ≤ 10⁶, C = 1
• 20 de puncte: N * M ≤ 10⁶, C = 3

Exemplu

Cum se trimit solutii?