It must have a solution since we can have all digits equal to <code>k</code>.

Use string dp, store modulus along with length of number currently formed.

Is it possible to solve greedily using divisibility rules?