Подсчёт чисел в диапазоне с определённой суммой цифр

В программу передаётся неотрицательное целое значение s. Требуется написать программу, которая определит количество целых чисел в диапазоне от 0 (включительно) до 10^12 (не включая верхнюю границу), у которых сумма цифр равна s.

Формат входных данных На вход подаётся целое неотрицательное число s (0 ≤ s ≤ 110).

Пример 1: Ввод: 0 Вывод: 1

Пример 2: Ввод: 1 Вывод: 12

Пример 3: Ввод: 12 Вывод: 31824