玉米中学的学生社会实践的内容是去玉米田中种玉米。
玉米中学有 块不同的玉米田,这些玉米田编号从 到 ,且第 号玉米田与第 号玉米田相邻,特殊地,第 号玉米田与第 号玉米田相邻。
现在玉米中学购置了 种不同的玉米,为了美观,学校要求相邻的玉米田中不能种植同一种玉米,现在某想要知道种植玉米的方案总数。
由于某耐心有限,因此只需要你求出对 取模后的结果即可。
从文件 corn.in 中读入数据。
corn.in
一行两个整数 ,,表示玉米田的数量和玉米的种类数。
向文件 corn.out 中输出答案。
corn.out
一行一个整数,表示种植玉米的方案数对 取模后的结果。
4 2
2
设2种玉米为a,b
a
b
2种种植玉米的方案为:abab,baba
abab
baba
4 3
18
所有测试点满足:
1
3
4
5
6
7
8
9
10