This is my code:

import time
import sys
sys.setrecursionlimit(100000)

n = int(input("Enter N (for digits): "))
k = int(input("Enter K: "))

rangeVar = pow(k, n) - pow(k, n-1)
starter = pow(k, n) - rangeVar
counter = 0

start = time.clock()
def calc(i):
    global starter, rangeVar, counter, n, k

    temp = str(i)

    if i == pow(k, n):
        return counter
    else:
        for j in range(len(temp) - 1):
            if temp[j] == '0' and temp[j+1] == '0':
                counter += 1
        calc(i+1)

calc(starter)
end = time.clock()
print(rangeVar - counter)
print(end - start)