No.890 移調の限られた旋法

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 80
作問者 : trineutrontrineutron / テスター : QCFiumQCFium
7 ProblemId : 3169 / 出題時の順位表
問題文最終更新日: 2019-07-22 23:28:23

問題文

合唱団に所属しているオリオン君は12平均律の6音または8音からなる「移調の限られた旋法」を使った曲を歌うことになった。移調の限られた旋法とは、1オクターブより短い周期を持つ旋法のことである。オリオン君は$N$平均律の$K$音からなる移調の限られた旋法はいくつあるか知りたくなった。この問題は以下のように言い換えることができる。

円周上に等間隔に$N$個の点がある。ここから$K$個の点を選ぶとき、回転対称性を持つ選び方は何通りあるか。

$N$と$K$が与えられるので、$N$平均律の$K$音からなる移調の限られた旋法の個数を求めよ。答えは非常に大きくなる可能性があるため、答えを$10^9+7$で割った余りを求めよ。

入力

$N\ K$

入力は全て整数
$1 \le N \le 10^6$
$1 \le K \le N$

出力

$N$平均律の$K$音からなる移調の限られた旋法の個数を$10^9+7$で割った余りを出力してください。最後に改行してください。

サンプル

サンプル1
入力
12 8
出力
15

サンプル2
入力
12 7
出力
0

サンプル3
入力
12 6
出力
24

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。