ЗАДАЧА A

Цифры числа

Имя входного файла:digits.in
Имя выходного файла:digits.out
Ограничение по времени:1 секунда
Ограничение по памяти:64 Мб

Задано число N. Посчитайте количество N-значных чисел, у которых сумма цифр меньше произведения цифр.
Так как ответ может быть очень большим, то надо вывести всего навсего остаток от деления этого ответа на 10^9+7.

Входные данные

Единственная строка входного файла содержит одно целое число N (1<=N<=50)

Выходные данные

В выходной файл следует вывести единственное число – количество N-значных чисел, у которых сумма цифр меньше произведения цифр.

Пример


digits.in digits.out
2
63