Compare Cost

(難易度目安:点)

長さの自然数のみから構成される数列を考えます。

ただし、の要素は以下の制約を満たします。

◉

また、数列の「コスト」を以下で定義します。

◎

条件を満たす数列は全てで個考えられますが、この全てに対し数列のコストを計算し、その期待値をで求めてください。

・

・入力はすべて整数

入力は以下の形式で与えられます。

N K 

求める期待値をとすると、は互いに素で分母がで割り切れないような既約分数の形で表せます。

とする時、を出力してください。

最後に改行してください。

3 2

750000009

考えうる数列は通り存在し、その全てについてコストを計算すると以下のようになります。

したがって、コストの期待値はであり、そのでの値を出力します。

6 10

750000063

期待値はです。

8 8

250000091

期待値はです。

200000 200000

907299983

期待値はです。