8517번 - Zbiory 다국어

문제

Masz dane n zbiorów, z których i-ty zawiera liczby a_i·d_i, (a_i+1)·d_i, (a_i+2)·d_i, …, b_i·d_i 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 ≤ 10⁹). Każdy z kolejnych n wierszy zawiera liczby całkowite a_i, b_i, d_i pooddzielane pojedynczymi odstępami (1 ≤ a_i,b_i,d_i ≤ 10¹⁸, a_i ≤ b_i, b_i·d_i ≤ 10¹⁸).

출력

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

제한

힌트