No.377 Background Pattern
EmKjp
紙ぺーぱーProblem Statement
We have decided to create an image of height $H$ and width $W$, and to make an infinitely extending background pattern by repeatedly placing it vertically and horizontally.
There are $K$ colors, numbered from $0$ to $K-1$, and each of the $W \times H$ pixels of the image is assigned one of the $K$ colors.
For example, the background pattern obtained by repeatedly placing the image of height 2 and width 3
123 456is as follows.
123123123123123123 456456456456456456 123123123123123123 456456456456456456 123123123123123123 456456456456456456 (無限に同じパターンが続きます）Write a program that outputs the number of background patterns that can be generated from images of height $H$ and width $W$, modulo $10^9 + 7$.
Here, background patterns that become exactly identical under a translation are considered the same.
For example, the background patterns obtained from the following 6 images are all treated as the same.
123 231 312 456 564 645 456 564 645 123 231 312
Input
H W K
$1 \le H \le 10^9 $
$1 \le W \le 10^9 $
$1 \le K \le 10^9 $
Output
Output the number of background patterns that can be generated, modulo $10^9 + 7$. Print a newline at the end.
Sample
Sample 1
Input
2 2 1
Output
1
Since only one color can be used, the only background image that can be made is one filled entirely with that single color.
Sample 2
Input
2 2 2
Output
7
The following 7 background patterns can be generated.
111111 101010 111111 101010 111111 101010 000000 111111 010101 010101 000000 000000 101010 000000 111111 101010 111111 101010 111111 101010 000000 111111 010101 010101 000000 000000 101010 000000 111111 101010 111111 101010 111111 101010 000000
Sample 3
Input
1 3 3
Output
11
The following 11 background patterns can be generated.
000000 001001 011011 111111 112112 122122 222222 220220 200200 120120 021021 000000 001001 011011 111111 112112 122122 222222 220220 200200 120120 021021 000000 001001 011011 111111 112112 122122 222222 220220 200200 120120 021021 000000 001001 011011 111111 112112 122122 222222 220220 200200 120120 021021 000000 001001 011011 111111 112112 122122 222222 220220 200200 120120 021021
Sample 4
Input
5 7 10
Output
878302877
Sample 5
Input
111 222 333
Output
91610936
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。