- All Contests
- ProjectEuler+
- Project Euler #203: Squarefree Binomial Coefficients

# Project Euler #203: Squarefree Binomial Coefficients

# Project Euler #203: Squarefree Binomial Coefficients

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

The binomial coefficients can be arranged in triangular form, Pascal's triangle, like this:

It can be seen that the first eight rows of Pascal's triangle contain twelve distinct numbers:

, , , , , , , , , , and .

A positive integer is called squarefree if no square of a prime divides . Of the twelve distinct numbers in the first eight rows of Pascal's triangle, all except and are squarefree. The sum of the distinct squarefree numbers in the first eight rows is .

Find the sum of the distinct squarefree numbers in the first rows of Pascal's triangle.

Since the answer can be huge, output it modulo .

**Input Format**

First line of each test file contains a single integer which is the number of queries per this file. lines follow each containing a single integer that is the number of the rows in the Pascal's triangle.

**Constraints**

**Output Format**

Output exactly lines with the answer modulo for the -th query on -th line.

**Sample Input 0**

```
1
8
```

**Sample Output 0**

```
105
```

**Explanation 0**

mod