说明

样例

3 3 10
ban
ana
nab

2/27

提示

【样例解释】 

样例一中，一次操作共有 16 种可能，其中得到 aa 的概率是 1/8，得到 ab 的 概率是 3/8，得到 bb 的概率是 1/8，得到 ba 的概率是 3/8。两次操作结果相同的 概率是 5/16。 

【数据规模和约定】 

30%的测试数据：M, N ≤ 10，K ≤ 100。 

50%的测试数据：M = N。 

100%的测试数据：1 ≤ M, N ≤ 500，2 ≤ K ≤ 10⁹。