解题思路：组合计算的逆向思维法，发疯方案数F=总方案数S-不发疯方案数N。
不发疯方案数计算：第一间牛舍有m选择，第二间有m-1选择，同样第三间有m-1选择 ， 总方案数
，因此
需要注意的是题目中的n很大，求一个数的n次幂，当n很大时用循环求取会超时，需采用快速幂算法。
快速幂是一种典型的分治算法。当我们要求时，可以先求出
，那么
，同样的道理求取x时，可以先求
，再做平方。特别注意，当n为奇数时，
递归快速幂模板：
long long ksm(ll n,ll m)/**< 求n的m次幂，注意快速幂算法尽量用longlong类型 */
{
if(m==1)
return n%mod;
long long temp;
temp=ksm(n,m/2);/**< temp是n的m/2次幂 */
temp=temp*temp%mod;
if(m%2==1) /**< 如果m是奇数，那要多乘1个n */
temp=n*temp%mod;
return temp;
}?另一种写法：可以注意到上面的递归算法是单递归算法，这类递归一般也能用循环方式来解决。
此处用到了二进制位的知识。举例说明：n的11次幂，11的二进制1011
n的11次幂可以看成是?，因为二进制第三位是0，所以没有
。用循环依次获得
.......，选择需要的进行乘法，比如11我们会选择
。
long long ksm(ll n,ll m)
{
ll ans=1;
while(m) /**< 可以用十进制11，即二进制 1011来模拟和思考 */
{
if(m&1)/**< 二进制最后一位是1，奇数 */
ans=ans*n%mod;
n=n*n%mod; /**< n成为n^2,再循环会变成n^4,n^8...... */
m=m>>1;/**< m右移一位 */
}
return ans;
}?本题目完整代码：
#include <iostream>
typedef long long ll;
using namespace std;
const ll mod=1000000007 ;
long long ksm(ll n,ll m)/**< 求n的m次幂，注意快速幂算法尽量用longlong类型 */
{
if(m==1)
return n%mod;
long long temp;
temp=ksm(n,m/2);/**< temp是n的m/2次幂 */
temp=temp*temp%mod;
if(m%2==1) /**< 如果m是奇数，那要多乘1个n */
temp=n*temp%mod;
return temp;
}
long long ksm2(ll n,ll m)
{
ll ans=1;
while(m) /**< 可以用十进制11，即二进制 1011来模拟和思考 */
{
if(m&1)/**< 二进制最后一位是1，奇数 */
ans=ans*n%mod;
n=n*n%mod; /**< n成为n^2,再循环会变成n^4,n^8...... */
m=m>>1;/**< m右移一位 */
}
return ans;
}
int main()
{
ll m,n;
cin>>n>>m;
cout<<(ksm(m,n)-m*ksm(m-1,n-1)%mod+mod)%mod;
return 0;
}
?
