C. k-мод

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

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

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

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

Саяхан сурагч Леша модны талаар лекц тавьсан. Лекцийн дараа Леша их урамшсан тул $k$-мод нэртэй өөрийн модоо авч ирсэн.

$k$-мод бол хязгааргүй үндэстэй мод юм:

  • орой бүр нь яг $k$ хүүхэдтэй байна;
  • ирмэг бүр өөрийн гэсэн жинтэй байна;
  • хэрвээ бид оройгоос хүүхэдрүү гарсан ирмэг харж байгаа бол (яг $k$ ирмэгүүд) тэдгээрийн жин нь $1, 2, 3, ..., k$ байна.

Дараах зурагт 3-модны хэсгийг харуулсан байна.

Удалгүй Лешагийн сайн найз Дима модны талаар олж мэдээд гайхсан байна: Нийт жин нь $n$ байх (замын ирмэгүүдийн бүх жингийн нийлбэр), $k$-модны үндэснээс эхлэн хамгийн багадаа $d$ жинтэй дор хаяж нэг ирмэг агуулсан хэдэн зам байгаа вэ?

Асуултынхаа хариултыг олоход нь Димад туслана уу. Арга замын тоо нь хэтэрхий их байж болох учраас $1000000007$ ($10^{9} + 7$) модулиар хэвлэнэ.

Оролт

Нэг мөрөнд зайгаар тусгаарлагдсан гурван бүхэл тоо $n$, $k$, $d$ ($1 ≤ n, k ≤ 100;$ $1 ≤ d ≤ k$) байна.

Гаралт

Нэг бүхэл тоо хэвлэнэ. Асуудлын хариулт нь $1000000007$ ($10^{9} + 7$) модулиар байна.

Орчуулсан: Даариймаа

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

Оролт
3 3 2
Гаралт
3
Оролт
3 3 3
Гаралт
1
Оролт
4 3 2
Гаралт
6
Оролт
4 5 2
Гаралт
7
Сэтгэгдлүүдийг ачааллаж байна...