Здравствуйте. Есть задача: на вход поступают числа A, B, S, T, k, где
1 <= A, B <= 10^19;
1 <= S, T <= 162;
2 <= k <= 100.
Нужно найти количество всех чисел, которые находятся на интервале [A, B], имеют сумму цифр, принадлежащих отрезку [S, T] и в то же время делятся на k без остатка.

Прямой перебор здесь не подходит. Как можно поступить в таком случае?