Problem #118

cntnmk

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

In cate moduri modulo 1 000 000 007 se poate colora o tabla de sah cu N randuri si M coloane (NxM) folosind K culori astfel incat oricare doua patrate alaturate sa aiba culori diferite?

Restrictii si precizari

  • 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

Explicatii

Exista 588 moduri de a colora o tabla 2 x 3 folosindu-se 4 culori.

General info

Uploader: liviu

Submissions