G - Divisors of Binomial Coefficient Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

二項係数 \displaystyle \binom{N}{K} の正の約数の個数を 998244353 で割った余りを求めてください。

制約

  • 1 \leq N \leq 10^{12}
  • 0 \leq K \leq \min(10^6,N)
  • 入力に含まれる値は全て整数である

入力

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

N K

出力

答えを出力せよ。

入力例 1

5 2

出力例 1

4

\displaystyle \binom{5}{2}=10 です。10 の正の約数は 1,2,5,10 の 4 個です。

入力例 2

103 3

出力例 2

8

\displaystyle \binom{103}{3}=176851 です。176851 の正の約数は 8 個あります。

入力例 3

1000000000000 1000000

出力例 3

110520107

Score : 600 points

Problem Statement

Find the number, modulo 998244353, of positive divisors of a binomial coefficient \displaystyle \binom{N}{K}.

Constraints

  • 1 \leq N \leq 10^{12}
  • 0 \leq K \leq \min(10^6,N)
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K

Output

Print the answer.

Sample Input 1

5 2

Sample Output 1

4

We have \displaystyle \binom{5}{2}=10, which has four positive divisors: 1,2,5,10.

Sample Input 2

103 3

Sample Output 2

8

We have \displaystyle \binom{103}{3}=176851, which has eight positive divisors.

Sample Input 3

1000000000000 1000000

Sample Output 3

110520107