yukicoder-377
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
{{{
#!html
<script type="text/x-mathjax-config">MathJax.Hub.Config({tex2jax: {inlineMath: [['$','$'], ['\\(','\\)']]}});</script>
<script type="text/javascript" async src="http://10.71.10.90/sfiction/tool/MathJax/MathJax-master/MathJax.js?config=TeX-MML-AM_CHTML"></script>
<style>
.input, pre {
display: block;
padding: 9.5px;
margin: 0 0 10px;
font-size: 13px;
line-height: 1.42857143;
color: #333;
word-break: break-all;
word-wrap: break-word;
background-color: #f5f5f5;
border: 1px solid #ccc;
border-radius: 4px;
}
</style>
}}}
== [https://yukicoder.me/problems/no/377 No.377 背景パターン] ==
=== Description ===
{{{
#!html
<p>生成一个高为$H$，宽为$W$的图像，把它往上下左右平铺，生成一个无穷大的背景。<br>
例如，下面这个高为$2$，宽为$3$的图像：
<pre>
123
456
</pre>
把它平铺后得到下面这个无穷大的背景
<pre>
...123123123123123123...
...456456456456456456...
...123123123123123123...
...456456456456456456...
...123123123123123123...
...456456456456456456...
</pre>
</p>
<p>现在每个$H \times W$的像素，你有$K$种颜色可以用来染色，求最后本质不同的背景数目$\bmod (10^9+7)$。两个背景如果可以通过平移变换变成一样，那么这两个背景会被当做同一个，例如下面这些都是同一个背景：<br>
<pre>
123 231 312 456 564 645
456 564 645 123 231 312
</pre>
</p>
}}}
=== Input ===
{{{
#!html
<p class="input">$H$ $W$ $K$</p>
<p>
$1 \le H, W, K \le 10^9$</p>
}}}
=== Output ===
{{{
#!html
<p>输出本质不同的背景数目$\bmod (10^9+7)$。</p>
}}}
=== Sample ===
==== Sample 1 ====
输入
{{{
#!html
<pre>
2 2 1
</pre>
}}}
输出
{{{
#!html
<pre>
1
</pre>
}}}
==== Sample 2 ====
输入
{{{
#!html
<pre>
2 2 2
</pre>
}}}
输出
{{{
#!html
<pre>
7
</pre>
有以下$7$种方案：
<pre>
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
</pre>
}}}
==== Sample 3 ====
输入
{{{
#!html
<pre>
1 3 3
</pre>
}}}
输出
{{{
#!html
<pre>
11
</pre>
有以下$11$种方案：
<pre>
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
</pre>
}}}
==== Sample 4 ====
输入
{{{
#!html
<pre>
5 7 10
</pre>
}}}
输出
{{{
#!html
<pre>
878302877
</pre>
}}}
==== Sample 5 ====
输入
{{{
#!html
<pre>
111 222 333
</pre>
}}}
输出
{{{
#!html
<pre>
91610936
</pre>
}}}No.377 背景パターン
Description
生成一个高为$H$，宽为$W$的图像，把它往上下左右平铺，生成一个无穷大的背景。
例如，下面这个高为$2$，宽为$3$的图像：
123456把它平铺后得到下面这个无穷大的背景
...123123123123123123......456456456456456456......123123123123123123......456456456456456456......123123123123123123......456456456456456456...
现在每个$H \times W$的像素，你有$K$种颜色可以用来染色，求最后本质不同的背景数目$\bmod (10^9+7)$。两个背景如果可以通过平移变换变成一样，那么这两个背景会被当做同一个，例如下面这些都是同一个背景：
123 231 312 456 564 645456 564 645 123 231 312
Input
$H$ $W$ $K$
$1 \le H, W, K \le 10^9$
Output
输出本质不同的背景数目$\bmod (10^9+7)$。
Sample
Sample 1
输入
2 2 1
输出
1
Sample 2
输入
2 2 2
输出
7有以下$7$种方案：
111111 101010 111111 101010 111111 101010 000000111111 010101 010101 000000 000000 101010 000000111111 101010 111111 101010 111111 101010 000000111111 010101 010101 000000 000000 101010 000000111111 101010 111111 101010 111111 101010 000000
Sample 3
输入
1 3 3
输出
11有以下$11$种方案：
000000 001001 011011 111111 112112 122122 222222 220220 200200 120120 021021000000 001001 011011 111111 112112 122122 222222 220220 200200 120120 021021000000 001001 011011 111111 112112 122122 222222 220220 200200 120120 021021000000 001001 011011 111111 112112 122122 222222 220220 200200 120120 021021000000 001001 011011 111111 112112 122122 222222 220220 200200 120120 021021
Sample 4
输入
5 7 10
输出
878302877
Sample 5
输入
111 222 333
输出
91610936