C 选择颜色

链接：https://ac.nowcoder.com/acm/contest/3211/C

题目描述 

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

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

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

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

输入描述:

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

输出描述:

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

示例1

输入

复制

4 3

输出

复制

18

示例2

输入

复制

1000000000 100

输出

复制

726

说明

对10007取模。

备注:

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

代码：

#include <bits/stdc++.h>
using namespace std;
long long n,c;
long long mod=10007;
int qpow(int a,int b)
{
    int ans=1;
    while(b)
    {
        if(b&1)
            ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
int main()
{
	cin>>n>>c;
	long long s;
	s=qpow(c-1,n);
	if(n%2==0)
	s+=c-1;
	else
	s-=c-1;
	cout<<s%mod;
}