Подсчитайте N-значные числа так, что каждая позиция делится на цифру в этой позиции

Учитывая положительное целое число N , задача состоит в том, чтобы подсчитать количество N -значных чисел, таких что каждый индекс (индексация на основе 1) в числе делится на цифру, встречающуюся в этом индексе. Так как двор может быть очень большим, выведите его по модулю 109+ 7.

Примеры:

Input: N = 2
Output: 2
Explanation: The numbers 11 and 12 are the only 2-digit numbers satisfying the condition.

Input: N = 5
Output: 24

Наивный подход: самый простой подход к решению задачи — сгенерировать все возможные N -значные числа и для каждого такого числа проверить, все ли его цифры удовлетворяют требуемому условию или нет.

Временная сложность: O(10 ^N *N)
Вспомогательное пространство: O(1)

Эффективный подход: чтобы оптимизировать описанный выше подход, идея состоит в том, чтобы учесть тот факт, что для каждой позиции существует 9 возможных вариантов от 1 до 9. Проверьте каждый возможный вариант и найдите результат.
Выполните следующие шаги, чтобы решить эту проблему:

• Инициализируйте переменную ans как 1 , чтобы сохранить ответ.
• Переберите диапазон [1, N], используя индекс переменной, и выполните следующие задачи:
  • Инициализируйте переменную, скажем, варианты как 0, чтобы сохранить количество вариантов для этого конкретного индекса.
  • Переберите диапазон [1, 9], используя переменную цифру , и выполните следующие задачи:
    • Если index%digit равен 0, то увеличьте значение вариантов на 1.
  • Установите значение ans как (ans*1LL*choices)%mod .
• После выполнения вышеуказанных шагов выведите значение ans в качестве ответа.

Ниже приведена реализация вышеуказанного подхода:

Временная сложность: O(10 * N)
Вспомогательное пространство: O(1)