github.com/captn3m0/codechef.git

---
category_name: easy
problem_code: CHEFMATH
problem_name: 'Chef and math'
languages_supported:
    - ADA
    - ASM
    - BASH
    - BF
    - C
    - 'C99 strict'
    - CAML
    - CLOJ
    - CLPS
    - 'CPP 4.3.2'
    - 'CPP 4.9.2'
    - CPP14
    - CS2
    - D
    - ERL
    - FORT
    - FS
    - GO
    - HASK
    - ICK
    - ICON
    - JAVA
    - JS
    - 'LISP clisp'
    - 'LISP sbcl'
    - LUA
    - NEM
    - NICE
    - NODEJS
    - 'PAS fpc'
    - 'PAS gpc'
    - PERL
    - PERL6
    - PHP
    - PIKE
    - PRLG
    - PYPY
    - PYTH
    - 'PYTH 3.4'
    - RUBY
    - SCALA
    - 'SCM chicken'
    - 'SCM guile'
    - 'SCM qobi'
    - ST
    - TCL
    - TEXT
    - WSPC
max_timelimit: '2'
source_sizelimit: '50000'
problem_author: omelyanenko
problem_tester: kevinsogo
date_added: 9-02-2016
tags:
    - dynamic
    - easy
    - may16
    - meet
    - omelyanenko
    - recursion
editorial_url: 'http://discuss.codechef.com/problems/CHEFMATH'
time:
    view_start_date: 1463391000
    submit_start_date: 1463391000
    visible_start_date: 1463391000
    end_date: 1735669800
    current: 1493558120
layout: problem
---
All submissions for this problem are available.###  Read problems statements in [Mandarin Chinese](http://www.codechef.com/download/translated/MAY16/mandarin/CHEFMATH.pdf), [Russian](http://www.codechef.com/download/translated/MAY16/russian/CHEFMATH.pdf) and [Vietnamese](http://www.codechef.com/download/translated/MAY16/vietnamese/CHEFMATH.pdf) as well.

Chef's team is going to participate at the legendary math battles. One of the main task in the competition is to calculate the number of ways to create a number by adding some Chefonacci numbers. A number is called a Chefonacci number if it is an element of Chefonacci sequence defined as follows.


<pre>
f(0) = 1; 
f(1) = 2; 
For i > 1 : f(i) = f(i - 1) + f(i - 2)

</pre>Chef asked you to help him with this task. There will be **Q** question of form **X, K** : How many different ways are there to create **X** by adding **K** Chefonacci numbers. Note that the order of numbers in the addition does not matter, i.e. (f(i) + f(j) + f(k)) and (f(j) + f(i) + f(k)) will not be counted as distinct ways. Also note that you are allowed to use a Chefonacci number any number of times (zero or more).

As the answer could be large, print your answer modulo **109 + 7 (1000000007)**.

### Input

First line of the input contains an integer **Q** denoting number of questions Chef was asked.

In the next **Q** lines follow the questions, i-th of the line will denote the i-th question represented by two space separated integer **X, K** respectively.

### Output

For each question, output a separate line containing the answer of the question.

### Constraints and Subtasks

**Subtask 1 : \[10 points\]** - **1** ≤ **Q** ≤ **50**
- **1** ≤  **X**  ≤ **109**
- **1** ≤  **K**  ≤  **4**


**Subtask 2 : \[20 points\]**

- **1** ≤ **Q** ≤ **100**
- **1** ≤  **X**  ≤ **109**
- **1** ≤  **K**  ≤  **5**


**Subtask 3 : \[20 points\]**

- **1** ≤ **Q** ≤ **100**
- **1** ≤  **X**  ≤ **102**
- **1** ≤  **K**  ≤  **10**


**Subtask 4 : \[50 points\]**

- **1** ≤ **Q** ≤ **100**
- **1** ≤  **X**  ≤ **109**
- **1** ≤  **K**  ≤  **10**

### Example

<pre>
<b>Input:</b>
5
12 1
13 1
13 2
13 3
13 4

<b>Output:</b>
0
1
1
2
4
</pre>### Explanation

**Example case 1.**
There is no way to create 12 by adding one Chefonacci number, as 12 is not a Chefonacci number.

**Example case 2.**
There is only one way to create 13 by adding one Chefonacci number, i.e. 13.

**Example case 3.**
There is one way to create 13 by adding two Chefonacci numbers, i.e. 5 + 8.

**Example case 4.**
There are two ways to create 13 by adding three Chefonacci numbers: 2 + 3 + 8, 3 + 5 + 5.

**Example case 5.**
There are four ways to create 13 by adding four Chefonacci numbers: 1 + 1 + 3 + 8, 1 + 2 + 2 + 8, 1 + 2 + 5 + 5, 2 + 3 + 3 + 5