AtCoder Regular Contest 034

C - 約数かつ倍数


Time limit時間制限 : 2sec / Memory limitメモリ制限 : 256MB

問題文

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


入力

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

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

部分点

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

  • 5 点分のテストケースは 1 ≦ B ≦ A ≦ 15 を満たす。
  • 別の 35 点分のテストケースは 1 ≦ B ≦ A ≦ 106, 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, 62 個存在する。


入力例2

15 4

出力例2

2592

入力例3

1000000 999900

出力例3

21398499

入力例4

1000000000 999999900

出力例4

745508745

Submit提出する