Î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.