C - 約数かつ倍数 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

2 個の正整数 A, B が与えられる。 A! の約数であり、かつ B! の倍数でもあるような正整数の個数を 1,000,000,007 で割った余りを求めよ。

入力

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

A B
  • 1 行目に、2 個の整数 A, B (1 ≦ B ≦ A ≦ 10^9, A - B ≦ 100) がスペース区切りで与えられる。

部分点

この問題には部分点が設定されている。

  • 5 点分のテストケースは 1 ≦ B ≦ A ≦ 15 を満たす。
  • 別の 35 点分のテストケースは 1 ≦ B ≦ A ≦ 10^6, A - B ≦ 100 を満たす。

出力

題意を満たす正整数の個数を 1,000,000,007 で割った余りを 1 行目に出力せよ。

末尾の改行を忘れないこと。

入力例1

3 2

出力例1

2

正整数 n に対し、 n! は n の階乗 n × (n - 1) × (n - 2) × ... × 1 を表す。

3! = 3 × 2 × 1 = 6 の約数であり、かつ 2! = 2 × 1 = 2 の倍数であるような正整数は 2, 6 の 2 個存在する。

入力例2

15 4

出力例2

2592

入力例3

1000000 999900

出力例3

21398499

入力例4

1000000000 999999900

出力例4

745508745