시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%

문제

Masz dane n zbiorów, z których i-ty zawiera liczby ai·di, (ai+1)·di, (ai+2)·di, …, bi·di Nazwijmy sumę tych wszystkich zbiorów S. Policz, ile jest w zbiorze  liczb, które są względnie pierwsze z daną liczbą m.

입력

W pierwszym wierszu znajdują się liczby n i m (1 ≤ n ≤ 16, 1 ≤ m ≤ 109). Każdy z kolejnych  n wierszy zawiera liczby całkowite ai, bi, di pooddzielane pojedynczymi odstępami (1 ≤ ai,bi,di ≤ 1018, ai ≤ bi, bi·di ≤ 1018).

 

출력

W jedynej linii wyjścia powinna znaleźć się jedna liczba całkowita, odpowiedź na pytanie z zadania.

예제 입력

3 6
1 5 2
7 5 3
3 5 7

예제 출력

2

힌트