Кино
Кинотеката Cinaplex има прикажувано N филмови - добитници на Оскар. По повод филмскиот фестивал “Оскаровски денови” кој трае M денови, Cinaplex треба да направи програма според која на секој ден од фестивалот ќе се прикажува точно еден од оскаровските филмови.
Програмата треба да ги задоволува следните правила:
- На фестивалот секој од дадените N оскаровски филмови мора да се прикаже најмалку еднаш.
- За да се овозможи програмата да е поразновидна, меѓу две прикажувања на ист филм мора да поминат најмалку D денови.
Утврдете на колку различни начини ќе може да се направи програмата на фестивалот за да бидат задоволени дадените правила. Бидејќи бројот на начини може да биде многу голем, дадете го остатотокот при делење на бројот на начини со 1 000 000 007.
Влез
Во првиот ред се наоѓа бројот N (1 <=N <= 100).
Во вториот ред се наоѓа бројот M (N <= M <= 100).
Во третиот ред се наоѓа бројот D(0 <= D <= N).
Забелешка:Во случаи кои носат 30% од поените ќе важи дека N, M < 10.
Излез
Во единствениот ред се печати остатокот при делење со 1 000 000 007 на бројот на начини на кои може да се направи програмата на фестивалот.
Ограничувања
Временско ограничување: 1 second
Мемориско ограничување: 64 megabytes
Примери
влез 1 3 0 | излез 1 |
влез 1 3 1 | излез 0 |
влез 3 4 1 | излез 18 |
Објаснување за првиот тест пример: Има само еден оскаровски филм кој може да се прикаже на сите 3 дена од фестивалот. Остатокот при делење на 1 со 1 000 000 007 е 1.
Објаснување за вториот тест пример: Оскаровскиот филм не може да се прикаже во два последователни дена, па оттука нема начин да се направи програма од 3 дена.
Објаснување за третиот тест пример: Ако првиот филм има ознака Ф1, вториот Ф2 и третиот Ф3 програмата може да биде: [Ф1 Ф2 Ф1 Ф3],[Ф1 Ф3 Ф1 Ф2], [Ф1 Ф2 Ф3 Ф1], [Ф1 Ф2 Ф3 Ф2], [Ф1 Ф3 Ф2 Ф1], [Ф1 Ф3 Ф2 Ф3], [Ф2 Ф1 Ф2 Ф3], [Ф2 Ф1 Ф3 Ф1], [Ф2 Ф1 Ф3 Ф2], [Ф2 Ф3 Ф1 Ф2], [Ф2 Ф3 Ф1 Ф3], [Ф2 Ф3 Ф2 Ф1], [Ф3 Ф1 Ф2 Ф1], [Ф3 Ф2 Ф1 Ф2], [Ф3 Ф1 Ф2 Ф3], [Ф3 Ф1 Ф3 Ф2], [Ф3 Ф2 Ф1 Ф3], [Ф3 Ф2 Ф3 Ф1]. Меѓу две прикажувања на ист филм има барем 1 ден на кој се прикажува друг филм.