Добрый вечер!

Не могу решить задачу K с этого контеста. После прочтения разбора все равно не понял.

Условие:

Вася готовит N шашлыков. В каждом шашлыке qi кусочков. Вася тратит 1 секунду, чтобы наколоть 1 кусок мяса. Когда он заканчивает накалывать i-ый шашлык, он сразу же приступает к (i+1)-ому.

Вася часто мечтает. Каждая мечта занимает ровно 1 секунду и он забывает наколоть кусочек мяса в эту секунду. Вася не мечтает два раза в любые последовательные (t+1) секунды.

Из-за того, что он мечтает, некоторые шашлыки могут быть не полные. Однако гости не будут злиться, если i-ый шашлык имеет не менее xi кусочков.

Требуется посчитать, сколькими способами может Вася мечтать в течении его работы, чтобы все посетители были довольны. Ответ вывести по модулю 10^9+7.

Ограничения:

1 <= N <= 1000, 0 <= t <= 100, 1 <= qi <= 250, 0 <= xi <= qi