Sets

Time limit1sMemory limit128 MB

Summary

Given n arithmetic-progression sets of multiples of d_i, count elements in their union that share no prime factor with m.

Level: Hard9 of 10
Topics: Math, Number theory, Combinatorics, Intervals
Solved: No attempts yet

Problem

You are given $n$ sets. The $i$ -th set contains the numbers

$a_i \cdot d_i,\ (a_i+1)\cdot d_i,\ (a_i+2)\cdot d_i,\ \ldots,\ b_i \cdot d_i$

Let $S$ be the union of all these sets. Count how many elements of $S$ are coprime with a given number $m$ (that is, whose greatest common divisor with $m$ equals $1$ ).

Input

The first line contains two integers $n$ and $m$ ( $1 \le n \le 16$ , $1 \le m \le 10^9$ ).

Each of the next $n$ lines contains three integers $a_i$ , $b_i$ , $d_i$ separated by single spaces ( $1 \le a_i, b_i, d_i \le 10^{18}$ , $a_i \le b_i$ , $b_i \cdot d_i \le 10^{18}$ ).

Output

Output a single integer: the number of elements of $S$ that are coprime with $m$ .

Examples6

Example 1
Input
```
3 6
1 5 2
3 7 5
3 5 7
```
Expected output
```
2
```
Example 2
Input
```
1 7
1 10 1
```
Expected output
```
9
```
Example 3
Input
```
2 1
1 3 1
2 5 1
```
Expected output
```
5
```
Example 4
Input
```
2 1
1 5 2
1 5 2
```
Expected output
```
5
```
Example 5
Input
```
1 12
1 12 1
```
Expected output
```
4
```
Example 6
Input
```
3 10
1 6 1
4 9 1
1 3 3
```
Expected output
```
4
```