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¹⁸).</p>

출력 형식

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

예제 입력

3 6
1 5 2
3 7 5
3 5 7

예제 출력

2