3674: 牛牛的 NOIP 商圈(第五轮04)
内存限制：256 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：1
解决：1
题目描述
牛牛有一个环形广场，广场上有首尾相连的N座建筑，它们围成一个环形。
即第1座建筑左侧是第N座建筑，右侧是第 2 座建筑。
第N座建筑左侧是第N − 1座建筑，右侧是第 1 座建筑。
对于其他的建筑第i座建筑左侧是第i − 1座建筑，右侧是第i + 1座建筑。
现在牛牛想要给这些建筑划分不同的商业功能，组成一个商圈。现在有四种不同 的商业建筑，分别为′N′, ′O′, ′I′, ′P′。
牛牛觉得， 如果连续相邻M建筑的功能相同，就会导致这一块区域的收益下降。 他想知道，在没有连续相邻M建筑的功能相同的情况下，他给这些建筑划分商业 功能的方案数有多少。
这个数字可能很大，你只用输出方案数对109 + 7取余数后的结果即可。
输入
仅一行，输入两个正整数N, M。
输出
仅一个整数，表示答案对109 + 7取余数后的结果。
样例输入 复制
3 2样例输出 复制
24提示
【样例 1 输入】
3 2
【样例 1 输出】
24
【样例 1 说明】
1 号建筑可以选择四种商业功能中的一种。
2 号建筑可以选择和 1 号建筑不同商业功能中的三种之一。
3 号建筑可以选择和 1 号建筑、2 号建筑不同商业功能中的两种之一。
所以答案为 4×3×2=24。
【样例 2 输入】
12 4
【样例 2 输出】
14486940
【数据范围】
对于 20%的测试数据，保证N ≤ 12。
对于 40%的测试数据，保证N ≤ 10^4 。
对于另外 10%的测试数据，保证M = 2。
对于 100%的测试数据，保证2 ≤ M ≤ 4, M < N ≤ 10^18 。