eolymp
bolt
Try our new interface for solving problems

k-Ağac

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 64 MiB

Təzəlikcə Bar ağaclar mövzusunda mühazirə dinlədi. Çox həvəslənən Bart öz fikrinə əsasən k-ağac adlandırdığı bir ağac icad etdi.

k-ağac – bu sonsuz kökü olan ağacdır.

  • hər bir təpə k oğul ehtiva edir

  • hər tilinin müəyyən çəkisi var

  • əgər hər hansı bir təpədən onun uşaqlarına gedən tilə (k tili) baxsaq, o zaman onların çəkisi 1, 2, 3 ..., k-ya bərabər olacaq.

Şəkildə 3-ağacın hissəsi göstərilib:

Bartın yaxın dostu Milhous ağac haqqında eşidən kimi düşünməyə başladı: “k-ağacın kökdən başlayaraq başlayaraq və ən azı d çəkili bir tili olan ümumi çəkisi (yoldadə olan bütün tillərin çəkilərinin cəmi) n olan neçə yol varʔ”

Milhousa bu suala cavab tapmaqda kömək et. Yolların sayının yetərincə böyük ola biləcəyini nəzərə alaraq, cavabı 1000000007(10^9 + 7) moduluna gırə verin.

Giriş verilənləri

Bir sətirdə boşluq ilə ayrılmış üç tam ədəd verilir: n, kd (1 ≤ n, k ≤ 100; 1 ≤ d ≤ k).

Bir sətirdə boşluq ilə ayrılmış üç tam ədəd verilir: n, kd (1 ≤ n, k ≤ 100; 1 ≤ d ≤ k).

Çıxış verilənləri

Məsələnin cavabını 1000000007 (10^9 + 7) moduluna görə verməli.

Məsələnin cavabını 1000000007 (10^9 + 7) moduluna görə verməli.

Nümunə

Giriş verilənləri #1
3 3 2
Çıxış verilənləri #1
3
Mənbə 2014 Azerbaijan - Zadeh cup