# Nemlit 的博客

By a konjac

### 题解 CF1097D 【Makoto and a Blackboard】

posted on 2019-10-03 23:36:12 | under 题解 |

$dp[i][j] = \sum_{l = 1}^x dp[i - 1][l] * \frac{1}{j}$

$sum[i][j] * sum[i][k] = sum[i][j * k](gcd(j, k) == 1)$

# $Code:$

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdlib>
using namespace std;
#define il inline
#define re register
#define int long long
#define mod 1000000007
il int read() {
re int x = 0, f = 1; re char c = getchar();
while(c < '0' || c > '9') { if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
return x * f;
}
#define rep(i, s, t) for(re int i = s; i <= t; ++ i)
#define mem(k, p) memset(k, p, sizeof(k))
#define maxn 1000005
int n, m, prim[maxn], tot, dis[maxn], dp[10005][50], ans, inv[100], Ans = 1;
il void get(int x) {
for(re int i = 2; i * i <= x; ++ i) {
if(x % i == 0) prim[++ tot] = i;
while(x % i == 0) x /= i, ++ dis[tot];
}
if(x != 1) prim[++ tot] = x, ++ dis[tot];
}
il int qpow(int a, int b) {
int r = 1;
while(b) {
if(b & 1) r = r * a % mod;
b >>= 1, a = a * a % mod;
}
return r;
}
signed main() {
n = read(), m = read();
get(n);
rep(i, 1, 60) inv[i] = qpow(i, mod - 2);
rep(T, 1, tot) {
mem(dp, 0), dp[0][dis[T]] = 1, ans = 0;
rep(i, 1, m) {
rep(j, 0, dis[T]) {
rep(k, j, dis[T]) dp[i][j] = (dp[i - 1][k] * inv[k + 1] % mod + dp[i][j]) % mod;
}
}
rep(i, 0, dis[T]) ans = (ans + dp[m][i] * qpow(prim[T] % mod, i) % mod) % mod;
Ans = ans * Ans % mod;
}
printf("%lld", Ans);
return 0;
}