numbers-of-interest-1

Harold always boasted about his prowess with numbers. So one day Reese challenged him to a problem. He gave Harold two numbers X and Y and asked him to find out the N^th number of the series which began with X numbers of Y’s and the following elements are equal to the sum of the last X numbers in the series. Help Harold find the  N^th number of the series. 

Input:
The first line contains a number T , number of test cases.
The next T lines each contain 3 integers X, Y and N separated by single space.

Output: 
For each test case print the N^th number of the sequence.

Constraints:
1 ≤ T ≤ 10^6
0 < N ≤ 50
0 < X < 50
0 ≤ Y< 3

Problem statement in native language :  http://hck.re/F91Yaz

SAMPLE INPUT
1
3 2 7

SAMPLE OUTPUT
34

Explanation

For X=3,Y=2 the series will be as follow:
2, 2, 2, 6, 10, 18, 34

Source: hackerearth | Difficulty: EASY
Tags: Fundamentals

Mathematics


Solutions:
def pro(x,y,n):
	a=[y]*x
	for i in range(n-x):
		
		a.append(sum(a[-x:]))
	return a[n-1]
for _ in range(eval(input())):
	x,y,n=list(map(int,input().split()))
	
	print(pro(x,y,n))
	


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
def nextNumber(arr, X) : 
	sum=0
	for n in reversed(arr) :
		if X > 0 :
			sum+=n
			X-=1
	return sum
 
def calculateNnumber(X,Y,N) :
	arr=[]
	for j in range(1,N+1) :
		if j <= X :
			arr.append(Y)
		else :
			arr.append(nextNumber(arr, X))
	return arr[-1]
	
T = int(input())
sol=[]
for i in range(0,T) :
	X,Y,N=list(map(int,input().split()))
	sol.append(calculateNnumber(X,Y,N))
	
for s in sol :
	print(s)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
tc =int(input())
for i in range(0,tc,1):
	input = input()
	arr = input.split()
	x = int(arr[0])
	y = int(arr[1])
	n = int(arr[2])
	if y==0 or n<=x:
		print(y)
	else:
		l = []
		for j in range(0,x,1):
			l.append(y)
		for k in range(len(l),n,1):
			s = 0
			for m in range(0,x,1):
				s = s + l[k-(m+1)]
			l.append(s)
		print(l[n-1])



tc = int(input())

def sumOfLastX(output, X):
	total = 0
	for i in range(len(output)-1, len(output)-X-1, -1):
		total += output[i]
	output.append(total)
	
while(tc):
	tc-=1
	inputs = list(map(int, input().split()))
	X=inputs[0]
	Y = inputs[1]
	N = inputs[2]
	
	output = []
	
	for i in range(X):
		output.append(Y)
	
		
	for i in range(N-X):
		sumOfLastX(output, X)
		

	print((output[N-1]))


for _ in range(int(input())):
	x,y,n=list(map(int,input().split()))
	l=list()
	for _ in range(x):
		l.append(y)
	s=0	
	for i in range(x-1,n):
		s=s+sum(l[i-(x-1):i+1])
		l.append(s)
		s=0
	print((l[-2]))






t = int(input())
while t>0:
	t-=1
	x, y, n = list(map(int, input().split()))
	ls = []
	for i in range(x):
		ls.append(y)
	for i in range(x, n):
		ls.append(sum(ls[-x:]))
	print(ls[-1])


t=eval(input())
for i in range(0,t):
	s=input().split()
	x=int(s[0])
	y=int(s[1])
	n=int(s[2])
	S=0
	if n>0 and n<=50 and x>=0 and x<50 and y>=0 and y<=3:
		A=[]
		for j in range(0,x):
			A.append(y)
		for j in range(x,n):
			k=sum(A[j-x:j])
			A.append(k)
		print((A[n-1]))
		
		


t = eval(input())
q=[]
o=[]
for i in range(0,t):
	l = input()	
	x = int(l.split()[0])
	y = int(l.split()[1])
	n = int(l.split()[2])

	q = [y for w in range(0,x)]
	for j in range(x,n):
		s = sum([q[z] for z in range(j-x,j)])
		q.append(s)
	o.append(q.pop())

for i in o:
	print(i)


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
tc =int(input())
for i in range(0,tc,1):
	input = input()
	arr = input.split()
	x = int(arr[0])
	y = int(arr[1])
	n = int(arr[2])
	l = []
	for j in range(0,x,1):
		l.append(y)
	for k in range(len(l),n,1):
		s = 0
		for m in range(0,x,1):
			s = s + l[k-(m+1)]
		l.append(s)
	print(l[n-1])



t=int(eval(input()))
for i in range(t):
	x,y,n=list(map(int,input().split()))
	k=[y]*x
	for i in range(n-x):
		k.append(sum(k[-x:]))
	print((k[-1]))
	

	


t = int(input())
for i in range(t) :
	test = list(map(int,input().split()))
	x,y,n = tuple(test)
	a = []
	a.extend([y] * x)
	index = 0
	for number in range(n-x) :
		a.append(sum(a[index:index+x]))
		index += 1
	print(a[-1])
		

	


from sys import stdin

inp = stdin.read().strip().split('\n')

seq = [[[] for y in range(3)] for x in range(50)]

for x in range(1, 50):
	for y in range(3):
		for i in range(x):
			seq[x][y].append(y)
		for i in range(50):
			seq[x][y].append(sum(seq[x][y][i:i + x]))

t = int(inp[0])
for i in range(t):
	x, y, n = list(map(int, inp[1 + i].split(' ')))
	print(seq[x][y][n - 1])


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
def result(n, x, y):
	a = [y] * 50
	for j in range(x, 50):
		a[j] = sum(a[j-x:j])
	return a[n-1]
t = eval(input())
a = []
for i in range(t):
	x, y, n =  list(map(int, input().split()))
	a.append(result(n, x, y))
for i in a:
	print(i)
	



tcs = input()
input_sets = []
for input_set in range(1, int(tcs) + 1):
	input_sets.append(input())


def generate_series(x, y, n):

	result = []
	result.append(y)
	result = result * x
	initial_len = len(result)
	final_len = n
	
	for iteration in range(1, (final_len - initial_len) + 1):
		sum = 0
		for i in result[len(result) - x:]:
			sum += i
		result.append(sum)
	print(result[-1])

1
for input_set in input_sets:
	x,y,z = input_set.split(' ')
	generate_series(int(x), int(y), int(z))


for _ in range(eval(input())):
	x,y,n=list(map(int,input().split()))
	lst=x*[y]
	
	for i in range(n-x):
		lst.append(sum(lst[-x:]))
			
	print(lst[n-1])


testcases = int(input())
for testcase in range(testcases) :
	test = list(map(int,input().split()))
	x,y,n = tuple(test)
	sequence = []
	sequence.extend([y] * x)
	index = 0
	for number in range(n-x) :
		sequence.append(sum(sequence[index:index+x]))
		index += 1
	print(sequence[-1])


testcases = int(input())
for testcase in range(testcases) :
	test = list(map(int,input().split()))
	x,y,n = tuple(test)
	sequence = []
	sequence.extend([y] * x)
	index = 0
	for number in range(n-x) :
		sequence.append(sum(sequence[index:index+x]))
		index += 1
	print(sequence[-1])


def findmagicnum(invar):
	listvar=invar.split(" ")
	finlist=[]
	x=int(listvar[0])
	y=int(listvar[1])
	n=int(listvar[2])
	for i in range(x):
		finlist.append(y)
	for i in range(len(finlist),n):
		varsum=sum(finlist[i-x:i])
		finlist.append(varsum)
	return finlist[len(finlist)-1]
	
testcases=input()
for i in range(int(testcases)):
	invar = input()
	print('%d'%(findmagicnum(invar)))


if __name__=="__main__":
	T=int(input())
	while(T):
		array=[0 for f in range (51)]
		i=0
		j=0
		arr=input()
		arr=arr.split()
		X=int(arr[0])
		Y=int(arr[1])
		N=int(arr[2])
		#print T,X,Y,N
		for o in range (X):
			array[o]=Y
		j=X
		array[j]=X*Y
		j=j+1
		while (j<N):
			array[j]=array[j-1]+array[j-1]-array[i]
			#print array[j]
			j=j+1
			i=i+1
		#print array
		print(array[N-1])
		T=T-1


#import math
def sum_series(arr):
	sum=0
	for i in arr:
		sum+=i
	return sum
		
times=eval(input())
for _ in range(times):
	in1=input()
	lst=in1.split()
	x=int(lst[0])
	y=int(lst[1])
	n=int(lst[2])
	if  n<=x:
		print(y)
	else:
		m=n-x
		ls=[y]*x
		
		while m>0:
			
			sum=sum_series(ls)
			new=ls[1:]
			
			new.append(sum)
			
			m-=1
			ls=new
		else:
			print(sum)
	
	
	
	
	
	#elif n<=2*x:
	#	m=n-x-1
	#	first=math.pow(2,m)*y
	#	second=first*(x-1)
	#	ans=int(second+y)
	#	print ans
	


T = int(input())
lst = []

def f(a,b,c):
	if c <= a:
		return b
	else:
		res = 0
		ls = [b for i in range(a)]
		c -= a
		i = 0
		while(c):
			n1 = 0
			for j in range(i,i+a):
				n1 = n1 + ls[j]
			res = n1
			ls.append(res)
			c -= 1
			i += 1
		return res
			
for i in range(T):
	x = input()
	y = x.split()
	t1 = int(y[0])
	t2 = int(y[1])
	t3 = int(y[2])
	r = f(t1,t2,t3)
	lst.append(r)
for i in range(T):
	print(lst[i])