| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 1 초 | 1024 MB | 38 | 21 | 16 | 51.613% |
JOI の春合宿が行われる施設の宿泊棟の部屋の鍵は,カードに穴がいくつか開いた形状をしている.穴 を開ける位置の候補は N 個あり,これらのうちいくつかに穴を開けた 2N 枚の異なる鍵が作られた.
あなたは,JOI の春合宿のための 1 枚以上 2N 枚以下の鍵をまとめて受け取った.穴を開ける候補の位置 を合わせて鍵を重ねてみたあなたは,ちょうど K か所,受け取ったすべての鍵に穴が開いている位置があ ることに気づいた.
このようなことが起こるような,受け取った鍵の組み合わせは何通りあるだろうか.答えを 1 000 000 007 (素数) で割った余りを求めよ.
N と K が与えられたとき,答えを 1 000 000 007 で割った余りを求めるプログラムを作成せよ.
標準入力から以下の入力を読み込め.
標準出力に鍵の組み合わせの個数を表す 1 行を出力せよ.出力の 1 行目には,答えを 1 000 000 007 で 割った余りを書け.
3 3
1
N = 3 の時,鍵は全部で 8 枚存在するが,ここでは以下のように鍵に名前をつける.
| 穴の開き方 | 名前 |
|---|---|
| φ | |
○しろまる |
A |
○しろまる |
B |
○しろまる |
C |
○しろまる○しろまる |
AB |
○しろまる○しろまる |
BC |
○しろまる ○しろまる |
AC |
○しろまる○しろまる○しろまる |
ABC |
たとえば ABC という 1 枚の鍵だけを受け取った場合,受け取ったすべての鍵に穴が開いている位置の 数は 3 か所である.また,それ以外の受け取り方では,受け取ったすべての鍵に穴が開いている位置の数 が 3 か所になることはない.したがって,条件を満たす鍵の受け取り方は 1 通りである.
3 2
6
{AB, ABC} という 2 枚の鍵を受け取った場合,受け取ったすべての鍵に穴が開いている位置の数は 2 か 所である.同様に,{AC, ABC}, {BC, ABC}, {AB}, {AC}, {BC} という受け取り方をした場合にも,受け取っ たすべての鍵に穴が開いている位置の数は 2 か所となる.
3 1
30
条件を満たす鍵の受け取り方は,{A}, {A, AB}, {A, AC}, {A, ABC}, {A, AB, AC}, {A, AB, ABC}, {A, AC, ABC}, {A, AB, AC, ABC}, {AB, AC}, {AB, AC, ABC} など 30 通りである.
3 0
218