Cho dãy số \(A = \lbrack a_{1},a_{2},\ldots,a_{n}\rbrack\) gồm \(n\) số nguyên không âm. Từ dãy số \(A\) xây dựng được các dãy số \(X = \left\lbrack x_{1},x_{2},\ldots,x_{k} \right\rbrack(1 \leq k \leq 10^{18})\) sao cho với hai phần tử liên tiếp \(x_{i}\) và \(x_{i + 1}\) bất kỳ \((1 \leq i \leq k - 1)\) số lượng bit 1 trong biểu diễn nhị phân của phép \(xor\ x_{i}\ \oplus x_{i + 1}\) chia hết cho 3.

Hai dãy được coi là khác nhau nếu tồn tại một vị trí trong dãy \(X\) àm ở đó hai phần tử khách nhau của dãy A được sử dụng, kết cả là khi hai phần tử này có cùng giá trị. Ví dụ, nếu \(A = \lbrack 1,1\rbrack\) và \(k = 1\), sẽ có 2 dãy thỏa mãn điều kiện của bài toán.

Lưu ý rằng với \(k = 1\) những dãy \(X\) gồm 1 phần tử luôn thỏa mãn.

Yêu cầu: Hãy đếm số dãy \(X\) được xây dựng từ dãy \(A\).

Do kết quả có thể rất lớn, bạn chỉ cần tính kết quả theo modulo 998244353

Dữ liệu vào:

+ Dòng thứ nhất chứa hái số nguyên \(n\) và \(k\ \left( 1 \leq n \leq 100,\ 1 \leq k \leq 10^{18} \right)\) cho biết độ dài của dãy \(A\) và \(X\).

+ Dòng thứ hai ghi lần lượt \(n\) số nguyên \(a_{1},a_{2},\ldots,a_{n}\ (0 \leq a_{i} \leq 10^{18})\)

Kết quả:

+ Ghi một số nguyên duy nhất là số lượng dãy \(X\) thỏa mãn điều kiện đề bài modulo 998244353.

Ví dụ:

Ràng buộc:

+ Subtask 1 (24%): \(k \leq 10^{5}\)

+ Subtask 2 (12%): \(n \leq 3\)

+ Subtask 3 (12%): \(a_{1} = a_{2} = \ldots. = a_{n}\)

+ Subtask 4 (12%): Với mỗi \(1 \leq i \leq n\), tồn tại số nguyên không âm \(t_{i}\) sao cho \(a_{i} = 2^{t_{i}}\)

+ Subtask 4 (40%): không có ràng buộc gì thêm