huyhau6a2 có một băng số ~a~ gồm ~n~ số và dự định sẽ tặng cho một người bạn nhân dịp sinh nhật của bạn đó. Băng số này có tính chất rất đặc biệt, vì nếu cậu chọn bất kỳ số nguyên dương ~l~ nào từ ~1~ đến ~n~, thì cậu luôn có thể chọn ~l~ trong ~n~ số trên băng sao cho tổng các số cậu chọn chia hết cho ~3~.

Tuy nhiên, bằng một cách nào đó, duong3982 đã vẽ bậy lên băng số, giờ chỉ còn ~m~ số đầu tiên hiện rõ, còn lại thì không thể xác định được vì đã bị vẽ đè lên. huyhau6a2 giờ phải viết lại cho đủ ~n~ số trên băng nhưng vì có quá nhiều số nên cậu không thể nhớ rõ các số còn lại. Tuy nhiên, cậu biết rằng các số trên băng luôn là các số nguyên dương có giá trị từ ~1~ đến ~k~. Giờ cậu cần làm lại băng số, nhưng tự nhiên trong đầu lại nảy lên một bài toán: Với các điều kiện như trên, thì tồn tại bao nhiêu băng số thỏa mãn điều kiện mà cậu có thể tạo được?

Tất nhiên vì cậu còn phải làm cho xong quà sinh nhật nên bài toán này xin nhường lại các bạn!

INPUT

Dòng đầu tiên gồm một số nguyên dương ~t~ (~1 \le t \le 2 \times 10^4~) là số trường hợp thử nghiệm. Định dạng với mỗi trường hợp thử nghiệm được mô tả như sau:

• Dòng đầu tiên trong mỗi trường hợp thử nghiệm gồm ba số nguyên dương ~n, k, m~ (~1 \le n, k \le 10^{18}~, ~0 \le m \le min (n, 50)~).
• Dòng thứ hai trong mỗi trường hợp thử nghiệm gồm ~m~ số nguyên dương ~a_1, a_2, ..., a_m~ (~1 \le a_i \le k~) tương ứng với các số đầu tiên trên băng số của huyhau6a2. Trong trường hợp ~m = 0~ sẽ không có dòng này.

OUTPUT

In ra ~t~ dòng, dòng thứ ~i~ in ra duy nhất một số nguyên không âm là số lượng băng số huyhau6a2 có thể làm tương ứng với trường hợp thử nghiệm thứ ~i~. Vì kết quả có thể rất lớn nên bạn chỉ cần in ra kết quả sau khi chia lấy dư cho ~998244353~.

SUBTASKS

Gọi ~N~ là tổng ~n~ trong tất cả trường hợp thử nghiệm.

Số điểm của bạn cho mỗi test, sẽ tỷ lệ thuận với số test nhỏ bạn giải đúng. Lưu ý, bạn vẫn cần in đủ ~T~ dòng, nếu không, bạn có thể gặp lỗi Presentation Error.

SAMPLE INPUT

6
3 4 0
3 4 1
1
3 4 1
2
3 4 1
3
3 4 1
4
3 4 3
2 3 2

SAMPLE OUTPUT

13
2
4
5
2
0