E. Ксениа ба Комбинаторик

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Ксениа өвөл шалгалттай ба өнөөдөр тэрээр комбинаторик сурч байгаа. Энд түүний бодох ёстой нэгэн бодлого өгөгджээ.

Доорх нөхцөлийг хангах $n$ оройтой мод хэд байх вэ?:

  • Модны оройнууд $1$-с $n$ хүртэл дугаарлагдсан;
  • 1 дугаартай орой ихдээ 2 л өөр оройтой холбогддог ба бусад орой бүр нь ихдээ өөрөөсөө ялгаатай ихдээ 3 оройтой л холбогддог;
  • Аль ч 2 нь холбогдоогүй байх ихдээ k ширхэг (maximum matching) л орой олддог. Дараах тохиолдолд 2 модыг ялгаатай гэнэ: Ямар нэгэн $u,v$ оройнууд нэг модонд нь ирмэгээр холбогдсон ба нөгөөд нь ирмэгээр холбогдоогүй.

Өгөгдсөн $n,k$-н хувьд бодлогыг бодож Ксениад тусална уу. Бидний олох тоо маш том тоо байж болох тул $1'00'000'007 (10^9 + 7)$ тоонд хувааж үлдэгдлийг нь хэвлэнэ үү.

Оролт

Нэг мөрөнд $n, k (1\le n, k\le  50)$ тоонууд өгөгдөнө.

Гаралт

Бодлогын хариуг $1000000007$ тоогоор жишч хэвлэ.

Орчуулсан: Төрбат

Жишээ тэстүүд

Оролт
1 1
Гаралт
0
Оролт
2 1
Гаралт
1
Оролт
3 1
Гаралт
3
Оролт
4 2
Гаралт
12

Тэмдэглэл

If you aren't familiar with matchings, please, read the following link: http://en.wikipedia.org/wiki/Matching_(graph_theory).

Сэтгэгдлүүдийг ачааллаж байна...