No.1815 K-Coloring Problem
okkuu
沙耶花Python users are advised to submit with PyPy instead.
Update: Someone has now gotten AC with Python.
Problem Statement
Color an $N\times M$ grid using exactly $K$ colors.
All $K$ colors must be used.
Adjacent cells must not have the same color.
Output the number of colorings modulo $10^9+7$.
Input
$N\ M\ K$
$1\le N\le3$
$1\le M\le10^{18}$
$1\le K\le2\times10^5$
All inputs are integers.
Output
Output the number of colorings modulo $10^9+7$ on $1$ line.
Print a newline at the end.
Sample
Sample 1
Input
3 1 3
Output
6
There are $6$ ways to color a $3\times1$ grid using exactly $3$ colors.
Sample 2
Input
2 2 10
Output
0
It is impossible to use all $10$ colors on a $2\times2$ grid.
Sample 3
Input
3 50 4
Output
70331496
Output the number of colorings modulo $10^9+7$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。