問題一覧 > 通常問題

No.2365 Present of good number

レベル : / AI推定難易度 : 1800 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （AC するまで非表示） / 解いたユーザー数 90
作問者 : Kak1_n0_tane / テスター : logx shobonvip Carpenters-Cat comavius
お気に入りにしたユーザー ProblemId : 6685 / 自分の提出
問題文最終更新日: 2023-06-30 14:32:25
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 395 (順位表) の他の問題:

Problem Statement

Pina likes prime factorization.

By the way, a sequence of functions ${f_n}$ is defined as follows.

  • For an integer $A = p_1^{a_1} \cdot p_2^{a_2} \cdots p_m^{a_m}$ that is at least $2$, $f(A) = (p_1+1)^{a_1} \cdot (p_2+1)^{a_2} \cdots (p_m+1)^{a_m}$
    where $p_1{,}\ p_2{,}\ \dots p_m$ are distinct primes and $a_1{,}\ a_2{,}\ \dots a_m$ are integers at least $1$.
  • For an integer $A$ that is at least $2$, $f_1(A) = f(A)$
  • For integers $A{,}\ n$ that are at least $2$, $f_n(A) = f(f_{n-1}(A))$

Find $f_K(N)$. Since the answer can be very large, output the remainder when divided by $10^9+7$.

Input

$N\ K$

  • $2 \leq N \leq 10^5$
  • $1 \leq K \leq 10^{18}$
  • All inputs are integers.

    • Output

    Print a newline at the end.

    Sample

    Sample 1
    Input
    1001 1
    Output
    1344

    Since $1001 = 7 \cdot 11 \cdot 13$, we have $f_1(1001) = f(1001) = (7+1) \cdot (11+1) \cdot (13+1) = 1344$.

    Sample 2
    Input
    2 10
    Output
    294967268

    $f_{10}(2) = 4294967296$. The remainder when divided by $10^9+7$ is $294967268$, so output this value.

    提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。