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 ; for ( int i = 0 ; i <= n ; i ++ ) { powersModk [ i ] = st ; st *= 10 ; st %= mod ; }