Когда-то давно во Франции жил граф по имени Бутер де Бит. С момента, как он научился писать и рисовать, он прожил n лет и n - 1 зим. И с того самого момента он вёл дневник на длинной полоске пергамента, в котором описывал лета и зимы, свидетелем которых он был.

Каждое лето он записывал цифру от 0 до 9 , характеризующую, насколько солнечным было это лето. Зимы же граф Бутер описывал проще: если снега зимой было много, значит зима удалась, если снега было мало, значит зима вышла неудачной. Каждую удачную зиму он рисовал в своём дневнике снежинку после последней записанной цифры, а каждую неудачную он не рисовал ничего. Снежинка при этом выглядела следующим образом: * .

Много лет спустя некто Артур Бабаев нашел эту полоску пергамента. На нём были написаны n цифр, и между некоторыми из них были нарисованы снежинки, которые он воспринял как знак умножения. Он быстро посчитал получившееся число, но это было слишком просто для него.

Артур принадлежит к обществу Любителей Квантовой Механики и знает, что наша вселенная не единственна. Более того, в каждой параллельной вселенной жило по такому же графу Бутер де Биту, и единственное, в чём отличалось существование разных де Битов, это удачность зим, которые они переживали. А именно, каждая из 2 ^{n - 1} последовательностей удачных/неудачных зим встречалась ровно в одной вселенной. Аналогичным образом в каждой вселенной существовало по Артуру, нашедшему этот самый лист пергамента и посчитавшему значение выражения на нём.

Артур из нашей вселенной очень захотел посчитать сумму чисел, полученную Артурами из всех вселенных. Так как это число может быть очень большим, он будет доволен, если узнает только остаток от его деления на 10 ⁹ + 7 .

Заметим, что ни одного из Артуров не смутит ситуация, в которой один из образовавшихся на полоске сомножителей содержит ведущие нули. Например, полоска пергамента, на которой написана строка 01 * 02 , задаёт корректное выражение, значение которого равняется 2 .