コード
public class Spacetsk {
private final int MOD = (int) 1e9 + 7;
public int countsets(int L, int H, int K) {
if (K == 1) {
return ((L + 1) * (H + 1)) % MOD;
}
int N = Math.max(Math.max(L + 2, H + 2), K + 2);
int[][] nCm = new int[N][N];
for (int i = 0; i < N; i++) {
nCm[i][0] = 1;
for (int j = 1; j <= i; j++) {
nCm[i][j] = (nCm[i - 1][j - 1] + nCm[i - 1][j]) % MOD;
}
}
long ans = 0;
for (int lastX = 1; lastX <= L; lastX++) {
for (int lastY = 1; lastY <= H; lastY++) {
int gcd = gcd(lastX, lastY);
int launch = (L + 1 - lastX);
ans += (long) nCm[gcd][K - 1] * launch * 2;
ans %= MOD;
}
}
ans += (long) nCm[H + 1][K] * (L + 1);
ans %= MOD;
return (int) ans;
}
private int gcd(int a, int b) {
if (b == 0) {
return a;
}
return gcd(b, a % b);
}
}