1108 选择颜色 - 大连理工大学 DP·AC算法竞赛协会 ICPC集训队 Online Judge

1108: 选择颜色

时间限制：1.000s

内存限制：128MB

提交通过: 1 提交: 1 统计

题目描述

n个人排成一个环形，每个人要从c种颜色中选择一个。

牛牛希望相邻的人选择的颜色是不同的
问有多少种方案。

输出方案数对10007取模的结果。

人是有顺序的，环旋转同构算不同的方案。

输入格式

输入只有一行，包含用空格分开的两个整数，表示n和c。

备注：
对于所有数据： 3 <= n <= 1000000000, 3 <= c <= 100
20分： c <= 3
40分： c <= 4
70分： n <= 10000

输出格式

输出一行一个整数，表示答案。

样例输入

4 3

样例输出

提示/说明

对10007取模。

分类

分治算法

提交