## 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
``` DK...: 2019-05-16 20:26:32 If the last digits of the answer is ...00004 and k>=2, you should print 4 (no leading zeros is needed) 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..