問題一覧 > 通常問題

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

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 108
作問者 : trineutrontrineutron / テスター : QCFiumQCFium
11 ProblemId : 3169 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2022-04-26 01:55:47

問題文

合唱団に所属しているオリオン君は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

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。