Был обычный весенний вечер. За окном завывала метель. Бухгалтер Евгений скучал на работе и с грустью вспоминал о своих былых успехах на олимпиадах по программированию. В его школьные годы на олимпиадах давали не больше восьми задач, и, разглядывая график своих успехов на сайте Topforces, ему удалось подсчитать, что в \(v_1\) олимпиадах он решил ровно 1 задачу, в \(v_2\) олимпиадах — ровно 2, \(\ldots\), в \(v_8\) олимпиадах — ровно 8 задач (Евгений предпочитал не вспоминать об олимпиадах, на которых он ничего не решил). К концу рабочего дня в офисе не осталось чистой бумаги, а из всех электронных устройств включенным оставался только калькулятор. Нашему герою ничего другого не оставалось, кроме как ввести памятные ему числа в калькулятор: \(v_1 1 v_2 2 \ldots v_8 8\). Стоит заметить, что никаких пробелов и других разделителей на калькуляторе Евгения не было, поэтому он записал эти числа просто подряд, получив некоторое число \(N\). Кроме того, он был достаточно ленив, поэтому все \(v_i\) вводил без ведущих нулей, а если какое-то \(v_i\) равнялось нулю, то соответствующую пару \(v_i i\) он просто не вводил.

Например, если \(v_2 = 111\), \(v_3 = 1\), а все остальные \(v_i = 0\), то у Евгения получилось бы число \(N = 111213\).

Уйдя с работы, Евгений оставил калькулятор с введенным числом \(N\) на столе, чем и воспользовалась его любопытная коллега Марина. Она сразу догадалась, как образовано введенное число, и уже собиралась приступать к расшифровке, как вдруг поняла, что различных наборов \((v_1, \ldots, v_8)\), из которых можно было получить это число, может быть достаточно много. Так, приведенное выше число \(N\) может быть получено также и при \(v_1 = 11\), \(v_3 = 21\).

Марина попросила вас найти количество таких наборов по модулю числа \(1\,000\,000\,007 = 10^9 + 7\).

Компания «Nanosoft» готовится удивить мир принципиально новой игрой для смартфонов «Две башни». Ее ключевая особенность заключается в том, что играть в нее смогут даже самые маленькие дети. Во-первых, для управления используется всего одна кнопка. Во-вторых, проиграть просто невозможно (правда, игроку может надоесть часами нажимать на одну и ту же кнопку).

Игровое поле представляет собой бесконечную горизонтальную ленту, разбитую на ячейки, пронумерованные целыми числами слева направо (см. рис.). Изначально в ячейках с отрицательными номерами расположена армия монстров, у каждого из которых есть некоторое количество единиц здоровья. А именно, в ячейках \(-1, -2, \ldots, -K\) расположены монстры с 1 единицей здоровья, в следующих \(K\) ячейках (с номерами \(-(K+1), \ldots, -2K\)) расположены монстры с 2 единицами здоровья и так далее. Таким образом, для каждого целого положительного числа \(i\) в ячейке с номером \(-i\) изначально находится монстр с \(\left\lceil\frac{i}{K}\right\rceil\) единицами здоровья. Кроме того, на ленте расположены две башни, каждая из которых контролирует некоторый отрезок ленты: первой башне соответствуют все ячейки с \(A\) по \(B\) включительно, а второй - ячейки с \(C\) по \(D\) включительно (\(0 \leqslant A \leqslant B \lt C \leqslant D\)).

Например, при \(K = 3\), \(A = B = 1\), \(C = 3\), \(D = 4\) исходная позиция будет выглядеть следующим образом:

После очередного нажатия на кнопку происходит следующее. Сначала вся армия сдвигается на одну позицию вправо. Затем каждая башня производит выстрел по самому правому монстру, находящемуся в области ее видимости, отнимая у него единицу здоровья. Если у монстра отнимают последнюю единицу здоровья, он немедленно умирает и исчезает.

Игра заканчивается, как только впервые в ячейке с номером \(D + 1\) окажется монстр.

Как вы уже могли заметить, главная проблема игры заключается в том, что для выигрыша может потребоваться слишком много нажатий на кнопку, поэтому для некоторых особо сложных уровней решено ограничить возраст игроков, допускаемых к его прохождению. В связи с этим вам нужно определить, сколько нажатий на кнопку потребуется для победы на данном уровне, который описывается числами \(K\),\(A\), \(B\), \(C\) и \(D\).