Виталий очень странный человек. У него есть две любимые цифры a и b. Виталий называет целое положительное число хорошим, если в десятичной записи этого числа используются только цифры a и b. Виталий называет хорошее число замечательным, если сумма его цифр является хорошим числом.

Например, пусть у Виталия любимые цифры 1 и 3, тогда число 12 — не является хорошим, а числа 13 или 311 являются. Также число 111 — замечательное, а число 11 — нет.

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

Под длиной числа подразумевается количество цифр в его десятичной записи без лидирующих нулей.