1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
|
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <set>
#include <vector>
using namespace std;
const int INF = ~0u>>1;
typedef pair <int,int> P;
#define MID(x,y) ((x+y)>>1)
#define iabs(x) ((x)>0?(x):-(x))
#define REP(i,a,b) for(int i=(a);i<(b);i++)
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define mp make_pair
#define print() cout<<"--------"<<endl
typedef long long ll;
#define maxn 100005
const ll mod = 1000000009;
ll fac[maxn],A[maxn],B[maxn];
void init(){
fac[0] = 1;
for (int i = 1; i < maxn; i ++){
fac[i] = fac[i-1] * i % mod;
}
A[0] = B[0] = 1;
for (int i = 1; i < maxn; i++){
A[i] = A[i-1] * 691504013 % mod;
B[i] = B[i-1] * 308495997 % mod;
}
}
ll quick_mod(ll n,ll k,ll mod){
ll ret = 1;
n %= mod;
while (k){
if (k & 1) ret = ret * n % mod;
k >>= 1;
n = n * n % mod;
}
return ret;
}
ll solve(ll n, ll k){
ll ret = 0;
for (int r = 0; r <= k; r ++){
ll t = A[k - r] * B[r] % mod;
ll x = fac[k];
ll y = fac[k-r] * fac[r] % mod;
ll c = x * quick_mod(y, mod - 2, mod) % mod;
ll tmp = t * (quick_mod(t, n, mod) - 1) % mod
* quick_mod(t-1,mod-2,mod) % mod;
if (t == 1) tmp = n % mod;
tmp = tmp * c % mod;
if (r & 1) ret -= tmp;
else ret += tmp;
ret %= mod;
}
ll m = quick_mod(383008016,mod-2,mod);
ret = ret * quick_mod(m,k,mod) % mod;
ret = (ret % mod + mod) % mod;
return ret;
}
int main(){
int T;
ll n,k;
init();
cin >> T;
while (T--){
cin >> n >> k;
cout << solve(n,k) << endl;
}
return 0;
}
|