NACCI - Nacci Fear

no tags 

We all know about the classical fibonaaci series, Fibonacci series is F(n)=F(n-1)+F(n-2). For this question we call it a 2-Nacci series as a new element is calculated as the sum of the last 2 terms of the series. For fibonaaci we assume F(0)=0 and F(1)=1. We define as new series N-Nacci where F(n) is the sum of the last n terms and here we assume that F(0)=0, F(1)=1,F(2)=2... F(n-1)=(n-1). Your task is to calculate the last K digits of the Lth term of the N-Nacci series(no leading zeros needed).

 

Constraints

 

2<=N<=30

K<=8

L<=1000000000

 

 

Input

The first line of the input denotes the number of test cases t(atmost 10). Each line denotes a test case consisting of N,K,L.

Output

For each test case print the last K digits of the Lth term of the N-Nacci series.

Example

Input:
4
2 1 5
3 6 12
4 1 10
4 2 10

Output:
5
778
6
16

hide comments
Soma: 2015-02-24 18:35:08

suppose if lth term is 123400005 and k is 3 should i print 005 or 5 ? (i am actually printing 5 but got WA).

Nikhil Verma: 2014-09-29 04:13:46

it's written we have to print k digits of the lth term... 778 is the 13th term i guess...
0,1,2,3,6,11,20,,37,68,125,230,423,778...
and 5 is the 5 the term
0,1,2,3,5...
which 1 to print :/

Last edit: 2014-09-29 04:14:10
devu: 2012-08-03 07:58:01

Dont do typecasting errors ,costed me 3 wrong answers!!

Himanshu Srivastava: 2012-06-30 22:10:32

can k=0??
dnt knw why i am getting wrong answer....

Last edit: 2012-06-30 22:23:28
Saransh Bansal: 2011-03-15 09:15:18

for the first test case we calculate the normal fibonacci series.. where F(0)=0 F(1)=1 F(2)=1 F(3)=2 F(4)=3 F(5)=5 so last 1 digit of F(5) is 5

for second case F(0)=0 F(1)=1 F(2)=2 F(3)=3 F(4)=6 F(5)=11 F(6)=20... F(12)=778

as the number has less than 6 digits print it as no leading zeros required

cegprakash: 2011-03-14 18:18:30

explanation for the testcases plz..


Added by:Saransh Bansal
Date:2011-03-09
Time limit:0.105s-0.476s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem