Submission #3261324

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long llint;
#define FOR(i, a, b) for(llint i = a; i <= b; ++i)
#define REP(i, n) for(llint i = 0; i < n; ++i)

const llint maxSUM = 111'111;
const llint mod = 1'000'000'007;

llint fact[maxSUM + 1];
llint inv[maxSUM + 1];

void scale(llint &value) {
    value %= mod;
}

llint fastExp(llint a, llint n) {
    if (a == 0) {
        return 0;
    }
    llint res = 1;
    while (n > 0) {
        if (n & 1) {
            res = res * a % mod;
        }
        a = a * a % mod;
        n >>= 1;
    }
    return res;
}

void preProcess() {
    fact[0] = 1;
    FOR(i, 1, maxSUM) {
        fact[i] = fact[i - 1] * i;
        scale(fact[i]);
        inv[i] = fastExp(fact[i], mod - 2);
        scale(inv[i]);
    }
}

llint combination(llint N, llint K) {
    llint res = inv[K] * inv[N - K];
    scale(res);
    res *= fact[N];
    scale(res);
    return res;

}

llint double_combination(llint sum, llint nTerms) {
    llint N = sum + nTerms - 1; // <= 30 + 10^5 - 1
    llint K = nTerms - 1; // <= 10^5 - 1
    return combination(N, K);
}

void run() {
    llint ans = 1, n, m;

    preProcess();
    cin >> n >> m;

    for (llint p = 2; p * p <= m; ++p) {
        if (m % p == 0) {
            llint deg = 0;
            while (m % p == 0) {
                m /= p;
                deg += 1;
            }
            ans *= double_combination(deg, n);
            scale(ans);
        }
    }

    if (m > 1) {
        ans *= double_combination(1, n);
        scale(ans);
    }

    cout << ans << "\n";
}

static void run_with_stack_size(void (*func)(), size_t stackSize) {
    char *stack, *send;
    stack = (char*) malloc(stackSize);
    send = stack + stackSize - 16;
    send = (char*) ((uintptr_t) send / 16 * 16);
    asm volatile(
    "mov %%rsp, (%0)\n"
    "mov %0, %%rsp\n"
    :
    : "r" (send));
    func();
    asm volatile(
    "mov (%0), %%rsp\n"
    :
    : "r" (send));
    free(stack);
}

int main() {
#ifdef LOCAL
    freopen("input", "r", stdin);
#endif
    run_with_stack_size(run, 256*1024*1024);
#ifdef LOCAL
    fclose(stdin);
#endif
    return 0;
}

Submission Info

Test Cases