Since at each recursive step we increase the suffix length by 1 by placing digits at its leftmost position , we need powers of 10 modded with k , in order to fpos the new remainder efficiently
st = 1 NEW_LINE for i in range ( n + 1 ) : NEW_LINE INDENT powersModk [ i ] = st NEW_LINE st *= 10 NEW_LINE st %= mod NEW_LINE DEDENT