BoB003-E: Sakky Sequence

2 secs 1024 MB
kyaneko999's icon kyaneko999

問題

Sakky さんは以下のような数列 A1,A2,A_1,A_2,\dots を「Sakky 数列」と名付けました.

  • i=1i=1 のとき,Ai=XA_i=X
  • i>1i>1 のとき,ii の正の約数のうち ii より小さいものを k1,k2,,kpk_1,k_2,\dots,k_p として,Ai=i×Ak1×Ak2××AkpA_i=i\times A_{k_1}\times A_{k_2}\times\cdots\times A_{k_p}

整数 N,XN,X が与えられるので,i=1NAi\displaystyle\sum_{i=1}^{N}A_i の値を 109+710^9+7 で割った余りを求めてください.

制約

  • 入力はすべて整数
  • 1N1061\le N\le 10^6
  • 1X1091\le X\le 10^9

入力

入力は以下の形式で標準入力から与えられる.

N  XN\;X

出力

答えを整数で出力しなさい.

入出力例

入力例1
4 3
出力例1
90

A1=3A_1=3A2=2×A1=6A_2=2\times A_1=6A3=3×A1=9A_3=3\times A_1=9A4=4×A1×A2=72A_4=4\times A_1\times A_2=72 です.よって,3+6+9+72=903+6+9+72=90 を出力します.

入力例2
1000000 1000000000
出力例2
980081983

109+710^9+7 で割った余りを求めることに注意してください.

Submit


Go (1.21)