Нэг ангид нийт N сурагч байна. Тэдгээрээс M нь охид бөгөөд үлдсэн нь хөвгүүд юм.

Багш сурагчдыг нэг эгнээнд суулгахдаа дараах дүрмийг баримтлахыг хүсэв:

Ямар ч тохиолдолд K-аас олон охин дараалан зэрэгцэж сууж болохгүй.

Өөрөөр хэлбэл, K+1 болон түүнээс олон дараалсан охин байж болохгүй.

Сурагч бүр хоорондоо ялгаатай гэж үзвэл, дээрх нөхцөлийг хангах бүх боломжит суулгалтын тоог ол.

Хариуг 1,000,000,007 (10⁹+7) тоонд хуваасны үлдэгдлээр гарга.

Оролт:

Оролтын файлд нэг мөрөнд гурван бүхэл тоо өгөгдөнө: N M K

• N — нийт сурагчдын тоо
• M — охидын тоо
• K — дараалан сууж болох охидын дээд хэмжээ

Гаралт:

Нөхцөлийг хангах суулгалтын боломжит тоог нэг бүхэл тоогоор хэвлэнэ.

Хязгаарлалтууд:

• 1 ≤ N ≤ 1,000,000
• 0 ≤ M ≤ N
• 0 ≤ K ≤ N

Дэд бодлого

Жишээ:

Оролт-1

3 2 1

Гаралт-1

2

Тайлбар

Нийт 3 сурагчийн 2 нь охин.

K = 1 тул 2 охин дараалан сууж болохгүй.

Боломжит байрлалууд:

• Охин – Хүү – Охин
• Хүү – Охин – Охин ❌ (2 охин дараалан → болохгүй)
• Охин – Охин – Хүү ❌ (2 охин дараалан → болохгүй)

Гэхдээ сурагчид ялгаатай тул:

• Охидыг хооронд нь сольж болно → 2 янз

Иймд хариу = 2

Оролт-1

4 2 2

Гаралт-1

12