When N=0, no number is there, or 0 is there. a[0]=1
When N=1, there are k such numbers, or 1..k-1. a[1]=k-1
When N=2, there are k^2-k such numbers.
a[2]=>k^2-k
    =>(k-1)k
    =>(k-1)(k-1+1)
    =>(k-1)(k-1)+(k-1)*1
    =>(k-1)a[1] + (k-1)*a[0]
which can be used for all subsequent digits