Cerința
O matrice cu n linii şi m coloane se completează aleatoriu cu numerele \( 2^{1}, 2^{2},…, 2^{n\cdot m}\), fiecare număr fiind folosit o singură dată. Matricea se numeşte perfecta dacă produsul elementelor pe fiecare linie şi fiecare coloană este pătrat perfect. Să se afle câte matrice perfecte se pot forma.
Date de intrare
Fișierul de intrare perfecta.in conține pe prima linie numerele n şi m, separate prin spațiu.
Date de ieșire
Fișierul de ieșire perfecta.out va conține pe prima linie numărul matricelor perfecte cu n linii şi m coloane, modulo 1.000.000.007.
Restricții și precizări
- \( 1 ≤ n\cdot m ≤ 2.000\)
- \( n\leq m \)
- se acordă punctaje parţiale pentru următoarele cazuri: \( 1 ≤ n\cdot m ≤ 30\ \), \( n=2\ \), \( n=3\ \), \( 1 ≤ n\cdot m ≤ 120 \).
Exemplu:
perfecta.in
2 2
perfecta.out
0
Exemplu:
perfecta.in
4 6
perfecta.out
742652666