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.