[ARC009C] 高橋君、24歳
题意翻译
高桥君,24岁,是个学生(esu梗),过生日辣OwO!
他要给他的$N$个朋友们发请帖,但是手贱发错了$K$个人的请帖QAQ.
他现在十分橘促,问他的朋友们拿到的请帖组合一共有多少种可能。
#### 输入格式:
一行,输入$N$,$K$。
#### 输出格式:
一行,输出答案数mod$1,777,777,777$的值。
#### 数据范围:
$2≦N≦777,777,777,777,777,777$
$2≦K≦777,777$
题目描述
[problemUrl]: https://atcoder.jp/contests/arc009/tasks/arc009_3
高橋君は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 $ 行で出力せよ。
なお、最後には改行を出力せよ。 ```
3 2
```
```
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 $ になります。
```
5 3
```
```
20
```
```
4 4
```
```
9
```
```
8 4
```
```
630
```
```
777 77
```
```
1084428318
```