După aventura de pe Cetățuie, Alex este nehotărât: el nu dorește să se întoarcă acasă încă, dar nici nu știe unde să meargă în continuare. Lui i-a venit o idee ingenioasă: el cunoaște M alte obiective turistice din Jluc. Așadar, a decis să facă un poll, unde cei N prieteni ai lui pot să decidă pentru fiecare obiectiv dacă îi place sau nu. Apoi, el va alege o submulțime S de prieteni, și va asculta doar opiniile lor. Având acum toate răspunsurile prietenilor lui, Alex decide să folosească următorul algoritm: el ia în ordine, de la 1 la M, fiecare obiectiv turistic, și elimină din lista sa toate voturile prietenilor care nu se află în majoritate pentru obiectivul curent(în caz de egalitate, se consideră că cei care au votat că le place sunt în majoritate. La final, Alex va rămâne cu o singură opinie(chiar dacă poate să aparțină mai multor prieteni), și se va folosi de ea pentru a lua o decizie finală. Totuși, Alex se întreabă acum: pentru fiecare prieten i, care e numărul de submulțimi S care îl conțin pe i, asupra cărora, dacă este aplicat algoritmul de mai sus, la final rămâne opinia lui i. Deoarece acest număr poate fi mare, el dorește să afle doar restul împărțirii acestuia la MOD.
Date de intrare
Pe prima linie se vor găsi separate prin spații numerele N, M, MOD cu semnificația din enunț. Apoi, pe următoarele N se vor găsi câte M numere, valoarea j de pe linia i având valoarea 1 dacă prietenului i i-a plăcut obiectivul j, și 0 altfel.
Date de ieșire
Se vor afișa N valori separate prin spațiu, al i-lea număr reprezentând răspunsul pentru prietenul i.
Restricţii
1 ≤ N ≤ 4 0001 ≤ M ≤ 1 0002 ≤ MOD ≤ 1 000 000 007, iarMODeste număr prim
Subtask 1 (6 puncte)
1 ≤ N ≤ 15și1 ≤ M ≤ 15
Subtask 2 (7 puncte)
1 ≤ N ≤ 20și1 ≤ M ≤ 40
Subtask 3 (45 puncte)
1 ≤ N ≤ 200și1 ≤ M ≤ 200
Subtask 4 (42 puncte)
- Fără restricții adiționale
Exemple
stdin
3 2 11
10
11
10
stdout
3 3 3
Explicații
Pentru submulțimea de prieteni formată din primii 2 termeni 10, 11 după primul obiectiv submulțimea nu se modifică, dar la al doilea obiectiv primul va fi eliminat din ea deoarece face parte din minoritate.