recursive-function

Implement the recursive function given by the following rules and print the last 3 digits:

F(x, y) = {
  y + 1 when x = 0,
  F(x - 1, 1) when x > 0 and y = 0,
  F(x - 1, F(x, y - 1)) when x > 0 and y > 0
}  

Input Format
A single line containing two integers X,Y
1 ≤ X,Y ≤ 100000  

Output Format
The last three digits  

Input Constraints
X and Y are non-negative integers.
Problem Setter: Practo Tech Team

SAMPLE INPUT
1 100

SAMPLE OUTPUT
102

Explanation

Note: x and y are non-negative integers

Source: hackerearth | Difficulty: EASY


Solutions:
def solve(x, y):
	if x == 0:
		return (y + 1) % 1000
	if x == 1:
		return (y + 2) % 1000
	if x == 2:
		return (2 * y + 3) % 1000
	if x == 3:
		r = 5
		add = 8
		for i in range(y):
			r = (add + r) % 1000
			add = (add * 2) % 1000
		return r
	if x == 4 and y == 0:
		return 13
	if (x == 4 and y == 1) or (x == 5 and y == 0):
		return 533

	return 733
	
x, y = list(map(int, input().split()))
print('%03d' % solve(x, y))


def F(x,y):
	if(x==0):
		return (y + 1)%1000
	if(str(x)+"-"+str(y) in d):
		return d[str(x)+"-"+str(y)]
	if x > 0 and y == 0:
		d[str(x)+"-"+str(y)] = F(x - 1, 1) % 1000
		return d[str(x)+"-"+str(y)]
	if x > 0 and y > 0:
		d[str(x)+"-"+str(y)] = F(x - 1, F(x, y - 1)) 
		return F(x - 1, F(x, y - 1)) 
x,y = list(map(int,input().split()))
d = dict()
ans = F(x,y)
if ans<10:
	print("00"+str(ans))
elif ans<100:
	print("0"+str(ans))
else:
	print(ans)


x,y= list(map(int,input().split()))
dp= [[-1 for i in range(1001)] for i in range(1001)]
def f(x,y):
	if x==0: return (y+1)%1000 
	if y==0 and x>0:
		if dp[x-1][1]==-1:
			dp[x-1][1]= f(x-1,1)%1000
		return dp[x-1][1]		
	if x>0 and y>0:
		if dp[x][y-1]==-1:
			dp[x][y-1]= f(x,y-1)%1000
		if dp[x-1][dp[x][y-1]]==-1:
			dp[x-1][dp[x][y-1]%1000]= f(x-1,dp[x][y-1]%1000)%1000 
		return dp[x-1][dp[x][y-1]]
x= f(x%1000,y%1000)%1000   
if len(str(x))==1:
	print("00"+str(x))
elif len(str(x))==2:
	print("0"+str(x))
else: print(x)