-
Notifications
You must be signed in to change notification settings - Fork 519
/
1097D.go
51 lines (47 loc) · 897 Bytes
/
1097D.go
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
package main
import (
. "fmt"
"io"
)
// 参考 https://www.luogu.com.cn/blog/ouuan/solution-cf1097d
// github.com/EndlessCheng/codeforces-go
func CF1097D(in io.Reader, out io.Writer) {
const mod int64 = 1e9 + 7
inv := [51]int64{1: 1}
for i := int64(2); i < 51; i++ {
inv[i] = (mod - mod/i) * inv[mod%i] % mod
}
var n int64
var k int
Fscan(in, &n, &k)
ans := int64(1)
do := func(p int64, e int) {
f := [51]int64{}
f[e] = 1
for i := 0; i < k; i++ {
for j := e; j >= 0; j-- {
f[j] = (f[j+1] + f[j]*inv[j+1]) % mod
}
}
sum, pp := int64(0), int64(1)
for _, v := range f[:] {
sum = (sum + pp*v) % mod
pp = pp * p % mod
}
ans = ans * sum % mod
}
for i := int64(2); i*i <= n; i++ {
e := 0
for ; n%i == 0; n /= i {
e++
}
if e > 0 {
do(i, e)
}
}
if n > 1 {
do(n, 1)
}
Fprint(out, ans)
}
//func main() { CF1097D(os.Stdin, os.Stdout) }