NACCI - Nacci Fear

We all know about the classical Fibonacci 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 Fibonacci 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 (at most 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

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

hide comments
2021-07-25 04:30:47 Waseem Ahmed
Read how to generate the nth term of the regular Fibonacci Series using matrix operations before attempting to solve this problem.
2019-05-16 20:26:32 DK...
If the last digits of the answer is ...00004 and k>=2, you should print 4 (no leading zeros is needed)
2015-02-24 18:35:08 Soma
suppose if lth term is 123400005 and k is 3 should i print 005 or 5 ? (i am actually printing 5 but got WA).
2014-09-29 04:13:46 Nikhil Verma
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
2012-08-03 07:58:01 devu
Dont do typecasting errors ,costed me 3 wrong answers!!
2012-06-30 22:10:32 Himanshu Srivastava
can k=0??
dnt knw why i am getting wrong answer....

Last edit: 2012-06-30 22:23:28
2011-03-15 09:15:18 Saransh Bansal
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
2011-03-14 18:18:30 cegprakash
explanation for the testcases plz..
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.