Вася сидит на невыносимо скучном уроке математики. Чтобы развлечься, он выписал на листок бумаги n цифр в одну строку. После этого Вася стал выписывать разные способы поставить в строке между некоторыми цифрами плюсы («+») таким образом, чтобы получалось корректное арифметическое выражение; формально, никакие два плюса в таком разбиении не должны стоять рядом (между любыми двумя соседними плюсами должна стоять хотя бы одна цифра), и никакой плюс не может стоять в начале или в конце строки. Например, в строке 100500, способы 100500 (не ставить плюсов совсем), 1+00+500 или 10050+0 являются корректными, а способы 100++500, +1+0+0+5+0+0 или 100500+ являются некорректными.

Урок был длинным, и Вася выписал все корректные способы расставить в своей строке из цифр ровно k плюсов. В этот момент его развлечение было замечено, и Вася получил задание до конца урока вычислить сумму значений всех получившихся арифметических выражений (при вычислении значения выражения ведущие нули в слагаемых следует игнорировать). Поскольку ответ может быть большим, Васе разрешили всего лишь получить остаток от деления ответа на 10⁹ + 7.