NACCI  Nacci Fear
We all know about the classical fibonaaci series, Fibonacci series is F(n)=F(n1)+F(n2). For this question we call it a 2Nacci 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 NNacci 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(n1)=(n1). Your task is to calculate the last K digits of the Lth term of the NNacci 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 NNacci series.
Example
Input: 4 2 1 5 3 6 12 4 1 10 4 2 10 Output:
5 778 6 16
hide comments
Soma:
20150224 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:
20140929 04:13:46
it's written we have to print k digits of the lth term... 778 is the 13th term i guess...


devu:
20120803 07:58:01
Dont do typecasting errors ,costed me 3 wrong answers!! 

Himanshu Srivastava:
20120630 22:10:32
can k=0??


Saransh Bansal:
20110315 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


cegprakash:
20110314 18:18:30
explanation for the testcases plz.. 
Added by:  Saransh Bansal 
Date:  20110309 
Time limit:  0.105s0.476s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 
Resource:  Own problem 