Cho số nguyên dương ~K~ và ~N~ tập hợp khác rỗng ~S_1, S_2, \dots, S_N~. Tập ~S_i~ ~(1 \le i \le N)~ gồm các phần tử khác nhau thuộc đoạn ~[0; 9]~. Người ta định nghĩa phép toán ~S_i - S_j~ là tập hợp gồm những phần tử chỉ thuộc tập ~S_i~ và không thuộc tập ~S_j~. Ví dụ: ~S_i = \{1, 3, 8\}~ và ~S_j = \{2, 9, 3\}~ khi đó ~S_i - S_j = \{1, 8\}~.

Dễ dàng nhận thấy phép toán trên không có tính kết hợp, tức là ~(S_i - S_j) - S_p \neq S_i - (S_j - S_p)~ nên chúng ta quy ước thứ tự thực hiện phép toán ~S_{i_1} - S_{i_2} - \dots - S_{i_m}~ là thực hiện từ phải qua trái. Ví dụ: ~(1, 2, 3) - (2, 3) - (1, 3) = (1, 2, 3) - (2) = (1, 3)~.

Yêu cầu: Hãy xác định số cách chọn các tập ~S_{i_1}, S_{i_2}, \dots, S_{i_m}~ ~(1 \le i_1 < i_2 < \dots < i_m \le N)~ từ tập ~S_1, S_2, \dots, S_N~ sao cho ~S_{i_1} - S_{i_2} - \dots - S_{i_m}~ được kết quả là tập có ít nhất ~K~ phần tử khác nhau.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~K~ ~(1 \le K \le 8)~ và ~N~ ~(2 \le N \le 50.000)~.
• ~N~ dòng tiếp theo, dòng thứ ~i + 1~ mô tả tập ~S_i~ chứa các số ~c_1, c_2, \dots, c_t~ trong đó ~t~ là số lượng phần tử của tập ~S_i~, ~c_1, c_2, \dots, c_t~ là các phần tử của tập ~S_i~.

Output

• Một số nguyên duy nhất là kết quả bài toán (lấy theo modulo ~123457~).

Sample Input 1

3 3
5 5 6 7 8 9
3 4 5 6
3 7 8 9

Sample Output 1

6