cntnmk

Time limit: 0.35s Memory limit: 64MB Input: Output:

În cate moduri modulo 1 000 000 007 se poate colora o tablă de șah cu N rânduri și M coloane (NxM) folosind K culori astfel încât oricare două patrate alăturate să aibă culori diferite?

Restricții și precizări

  • 1 ≤ N * M ≤ 90
  • 2 ≤ K ≤ 1 000 000
  • Pentru 75 de puncte N * M ≤ 80

Exemplu

stdin

2 3 4

stdout

588

stdin

7 5 182931

stdout

35823641

Explicații

Există 588 moduri de a colora o tablă 2 x 3 folosindu-se 4 culori.

Log in or sign up to be able to send submissions!