费马小定理求逆元

在模为素数p的情况下，有费马小定理
a^(p-1)=1（mod p）
那么a^(p-2)=a^-1(mod p)
也就是说a的逆元为a^(p-2)

而在模不为素数p的情况下，有欧拉定理
a^phi(m)=1（mod m） (a⊥m)
同理a^-1=a^(phi(m)-1)

牛牛和牛可乐的赌约
https://ac.nowcoder.com/acm/contest/7412/A
题目描述
牛可乐发明了一种n面骰子（点数分别从1{}1到{}nn，掷出每面的概率为\frac {1} {n}
n
1
​
）去给牛牛玩，因为牛牛是个欧皇，所以他想测试一下牛牛的人品，他告诉牛牛，让牛牛投m{}m次骰子，牛牛如果全部投出点数为{}nn的面就算牛牛赢，牛牛很相信自己的人品，就和牛可乐赌一包辣条，说自己肯定可以全部投出点数为{}nn点面，但是牛牛又有点害怕自己打赌输了，想让你提前帮他计算一下他输概率有多少？
输入描述:
有多组输入样例，第一行为样例组数t（t\leq 1×10^6）t（t≤1×10
6
）
接下来t行每行有一个整数n和m，分别表示骰子的面数和牛牛的投掷次数

（n,m<=1×10^9）（n,m<=1×10
9
）

输出描述:
输出t行，每行输出为分数p/q mod 1e9+7的形式

#include<bits/stdc++.h>
using namespace std;
const int v = 1e9 + 7;
long long pv(int a, int b, int mod) {
    long long base = a;
    long long ans = 1;
    while (b) {
        if (b & 1) ans = ans * base % mod;
        base = base * base % mod;
        b >>= 1;
    }
    return ans;
}
long long inv(int a,int mod){//求逆元
    return pv(a,mod-2,mod);
}
int main()
{
    int t;
    scanf("%d", &t);
    while (t--) {
        int n, m;
        scanf("%d%d", &n, &m);
        long long sum=pv(n,m,v);
        printf("%d\n", ((sum-1)*inv(sum,v))%v);
    }
}