P7538 [COCI 2016/2017 #4] Osmosmjerka
题目描述
给定一个 $M \times N$ 的字母矩阵，以下面的为例：
```plain
honi
hsin
```
接着我们将其进行无限延伸，得到：
```plain
...honihonihonihoni...
...hsinhsinhsinhsin...
...honihonihonihoni...
...hsinhsinhsinhsin...
```
在无限延伸后得到的新矩阵后，我们随机选取其中一个区域的字母，然后再沿着一定的方向连续读取 $K$ 个字母。在独立完成上述操作两次之后，我们会得到两个长度为 $K$ 的字符串。求两个字符串相同的概率。
输入格式
无
输出格式
无
说明/提示
**【数据规模与约定】**
对于其中 $100$ 分的数据，$M=N$。
对于 $100\%$ 的数据，$1 \le M,N \le 500$，$2 \le K \le 10^9$。
**【提示与说明】**
**题目译自 [COCI 2016-2017](https://hsin.hr/coci/archive/2016_2017/) [CONTEST #4](https://hsin.hr/coci/archive/2016_2017/contest4_tasks.pdf) _T6 Osmosmjerka_。**
**本题分值按 COCI 原题设置，满分 $160$。**