집합

$n$개의 집합이 주어집니다. $i$번째 집합은 다음 수들을 담고 있습니다.

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

이 모든 집합의 합집합을 $S$라고 합시다. 집합 $S$의 원소 중에서 주어진 수 $m$과 서로소인 (즉, $m$과의 최대공약수가 $1$인) 수가 몇 개인지 세어 주세요.

첫째 줄에 두 정수 $n$과 $m$이 주어집니다 ($1 \le n \le 16$, $1 \le m \le 10^9$).

이어지는 $n$개의 줄에는 각각 세 정수 $a_i$, $b_i$, $d_i$가 공백 하나로 구분되어 주어집니다 ($1 \le a_i, b_i, d_i \le 10^{18}$, $a_i \le b_i$, $b_i \cdot d_i \le 10^{18}$).

집합 $S$의 원소 중 $m$과 서로소인 원소의 개수를 한 줄에 정수 하나로 출력합니다.