C - 高橋君、24歳 解説 /

実行時間制限: 2 sec / メモリ制限: 64 MB

問題文

　高橋君は10月20日が誕生日なので、友達を誕生会に呼ぼうと考えています。
　そこで恥ずかしがり屋な彼は、みんなに招待状を送ることにしました。

　高橋君はなかなか手紙の良い文面が思いつかなかったので、全員分の手紙を書き終えたのは誕生日の前日でした。
　慌てて友達 N 人の家のポストに 1 つずつ手紙を入れていったのですが、誤ってそのうち K 人の手紙を、別の友達のポストに入れてしまいました。

　帰った後にそのことに気づいた高橋君はとても焦っています。
　彼を少しでも元気づけるために、ポストと入れられた手紙の考えられる組み合わせの数を 1,777,777,777 (素数) で割った余りを教えてあげてください。

入力

入力は以下の形式で標準入力から与えられる。 
N K
  • 入力は 1 行ある。
  • 1 行目には、高橋君の友達の人数を表す整数 N と高橋君が間違った手紙を入れてしまった友達の人数を表す整数 K が空白区切りで与えられる。
    • K は N を超えることはない。
  • 友達は過不足無く 1 人 1 枚の手紙を受け取った。
  • K 人は別の友達の手紙を受け取り、N-K 人は自分宛に書かれた手紙を受け取った。

部分点

テストデータは以下の 2 種類のテストデータセットのいずれかに含まれており、それぞれのデータセットに含まれているテストデータは以下に示すように与えられる整数 N と K の範囲が異なっている。
あるテストデータセットに含まれているテストデータ全てに対して正しい解を出力できると、それ以外のテストデータセットで不正解を出力しても以下のように部分点が与えられる。
  • small ( 40 点)
    • 2≦N≦8
    • 2≦K≦8
  • large ( 60 点)
    • 2≦N≦777,777,777,777,777,777
    • 2≦K≦777,777

出力

ポストと入れられた手紙の考えられる組み合わせの数を 1,777,777,777 (素数) で割った余りを標準出力に 1 行で出力せよ。
なお、最後には改行を出力せよ。

入力例 1

3 2

出力例 1

3
  • 高橋君の 3 人の友達を A,B,C とすると、次のような組み合わせが考えられます。
    1. A は自分宛の手紙を受け取り、B は C 宛ての手紙を受け取り、C は B 宛ての手紙を受け取った。
    2. B は自分宛の手紙を受け取り、A は C 宛ての手紙を受け取り、C は A 宛ての手紙を受け取った。
    3. C は自分宛の手紙を受け取り、B は A 宛ての手紙を受け取り、A は B 宛ての手紙を受け取った。
  • 条件を満たす組み合わせはこの 3 通りのみなので、答えは 3 になります。

入力例 2

5 3

出力例 2

20

入力例 3

4 4

出力例 3

9

入力例 4

8 4

出力例 4

630

入力例 5

777 77

出力例 5

1084428318

出典

ARC 009