Cho số nguyên dương ~N~, một xúc xắc đều ~M~ mặt được đánh số từ ~1~ đến ~M~ và một dãy ~A~ độ dài ~M~.

Bạn có một số nguyên ~X~. Ban đầu ~X~ bằng ~1~.

Bạn sẽ lăn xúc xắc liên tục nếu ~X~ còn nhỏ hơn ~N~. Nếu lăn xúc xắc ra mặt có đánh số là ~k~, ~X~ sẽ có giá trị mới bằng ~X×A_k~.

Yêu cầu: Đếm số cách để số ~X~ bằng ~N~ sau khi lăn xong theo mod ~998244353~.

Input

Dòng thứ nhất gồm ~2~ số nguyên dương ~N, M~ (~N \le 10^{18},~ ~M \le 100~)

Dòng thứ hai gồm ~M~ số nguyên biểu diễn mảng ~A~ (~2 \le A_i\le 10^6~)

Output

In ra kết quả là một số nguyên không âm là kết quả bài toán, vì đáp án có thể rất lớn nên hãy in ra số dư khi chia cho ~998244353~.

Scoring

Gọi ~K~ là phần tử lớn nhất trong dãy ~A~.

Có ~10\%~ số điểm với ~N \le 10^6,~ ~M \le 6~.

Có ~20\%~ số điểm khác với ~N \le 10^{18},~ ~M \le 6~.

Có ~30\%~ số điểm khác với ~N \le 10^{18},~ ~K \le 12~.

Còn lại không có điều kiện gì thêm.

Sample Input 1

12 11
2 3 4 5 6 7 8 9 10 11 12

Sample Output 1

8

Sample Input 2

2 2
2 2

Sample Output 2

2

Sample Input 3

123456 6
2 3 4 5 6 643

Sample Output 3

688