def permuation(A,B,C):
	n = len(A)
	
	#Ist Basecase; For n=0, F(0,B,C)=0 for any B
	if n==0:
		return 0
	
	#2nd BaseCase; For B>len(C), F(n,B,C)=0 for any C
	if B > len(str(C)):
		return 0
	
	#3rd BaseCase; For B=1, all digits in A less than C
	if B==1:
		ctr = 0
		while ctr<n and A[ctr] < C:
			ctr+=1
		return ctr
	
	#4th BaseCase; For B<len(C), if 0 is not present in A, then result is n^B
	#otherwise, if 0 is present then first digit can be chosen in (n-1)ways and rest of the digits in n ways
	if B < len(str(C)):
		if A[0]!=0:
			return n**B
		return (n-1)*(n**(B-1))

	C = map(int,list(str(C)))

	ans = 0

	#In case when B==len(C)
	for i in range(B):
		j = 0
		prev_mul = 0
		
		#For ith Digit, find digits less than C[i]
		while j < n and A[j] < C[i]:
			j += 1
		
		#For first Digit, 0 is present in A 
		if i==0 and A[0]==0:
			j -= 1

		ans += j*(n**(B-i-1))
		print "i:",i,j,n,(B-i-1),ans
		
		#if ith digit is not present in A, then no number can be made further
		if C[i] not in A:
			return ans
	print ans
	return ans

A = [0,1,5]
B = 1
C = 2
permuation(A,B,C)
A = [0,1,2,5]
permuation(A,2,21)
A = [2,4,5,9]
permuation(A,4,4321)
A = [0]
print "Ans:",permuation(A,1,5)
A = [0,1,2,5]
print "Ans:",permuation(A,1,123)
A = [2,3,5,6,7,9]
print "Ans:",permuation(A,5,42950)
A = [0,1,2,3,4,5,6,7,8,9]
print "Ans:",permuation(A,5,10004)

"""


Let us try to solve for all the possible cases.
Let d be size of A.

Case 1: If B is greater than length of C or d is 0 then no such number is possible.

Case 2: If B is smaller than length of C then all the possible combination of digits of length B are valid.

Generate all such B digit numbers.
For the first position we can’t have 0 and for ther rest of (B - 1) position we can have all d possible digits.
Hence, Answer = d B if A contains 0 else (d-1) * ( d )(B-1)

Case 3: If B is equal to length of C
Construct digit array of C ( call it as digit[]).

Let First(i) be a number formed by taking first i digits of it.
Let lower[i] denote number of elements in A which are smaller than i.
It can be easily computed by idea similar to prefix sum.

For example:

First(2) of 423 is 42. 
If  A =  [ 0, 2] then lower[0] = 0, lower[0] = 0, lower[1]  = 1,  lower[2] = 1, lower[3] = 2  

Generate B digit numbers by dynamic programming. Let say dp[i] denotes the total numbers of length i which are less than first i digits of C.

Elements in dp[i] can be generated by two cases :

i) For all the Numbers whose First(i - 1) is less than First (i-1) of C, we can put any digit at i’th index.
Hence, dp[i] += (dp[i-1] * d)

ii) For all the Numbers whose First (i - 1) is same as First (i - 1) of C, we can only put those digits which are smaller than digit[i] .

Hence , dp[i] += lower[digit[i]]

Final answer will be dp[B]

Remark:
For first index don’t include 0 if B is not 1 and dp[0] will be 0.

Time Complexity = O(B)
"""
