- All Contests
- ProjectEuler+
- Project Euler #148: Exploring Pascal's triangle.

# Project Euler #148: Exploring Pascal's triangle.

# Project Euler #148: Exploring Pascal's triangle.

_{This problem is a programming version of Problem 148 from projecteuler.net}

We can easily verify that none of the entries in the first seven rows of Pascal's triangle are divisible by 7:

However, if we check the first one hundred rows, we will find that only 2361 of the 5050 entries are *not* divisible by 7.

Find the number of entries which are *not* divisible by 7 in the first rows and first columns of Pascal's triangle. Here, "column" means a column when the triangle is written this way:

Since the answer can be very large, output it modulo .

**Input Format**

The first line of input contains , the number of test cases.

Each test case consists of one line containing two integers, and , separated by a space.

**Constraints**

Test files #01-#03:

Test files #04-#06:

Test files #07-#09:

Test files #10-#12:

Test files #13-#15: No additional constraints.

**Output Format**

For each test case, output a single line containing a single integer, the answer for that test case.

**Sample Input**

```
3
5 3
100 100
100 50
```

**Sample Output**

```
12
2361
1622
```

**Explanation**

In the first test case, the following are the entries in the first rows and first columns: (highlighted in bold)

There are entries all in all, and they are all not divisible by . Thus, the answer is .

The second test case is mentioned in the problem statement.