Ông già Noel có ~N~ loại quà, trong đó loại thứ ~i~ gồm ~a_i~ hộp quà giống nhau. Việc phát quà Noel cho các bé được ông thực hiện như sau:

1. Đầu tiên, ông già Noel chia toàn bộ các hộp quà vào ~M~ túi quà có sẵn, được ông xếp thành hàng ngang và đánh số từ ~1~ đến ~M~ (tăng dần từ trái sang phải).

2. Máy tính chọn ra ngẫu nhiên một cặp số (~L, R~) thỏa mãn ~1 \le L \le R \le M~, sau đó các túi quà có chỉ số từ ~L~ đến ~R~ sẽ được mang lên xe tuần lộc để phân phát cho trẻ em trên khắp thế giới. Lưu ý rằng, mọi cặp số (~L, R~) có xác suất được chọn là như nhau.

Ở bước 2, ta gọi số loại quà khác nhau trong các túi từ ~L~ đến ~R~ là độ đa dạng của chúng. Ta coi một túi không có quà có độ đa dạng là ~0~. Vì không muốn đứa trẻ nào nhận ra hai hộp quà giống nhau nên từ bước 1, ông già Noel sẽ chủ động chia quà vào các túi sao cho độ đa dạng đạt giá trị kỳ vọng lớn nhất.

Hãy giúp ông già Noel tính giá trị kỳ vọng lớn nhất của độ đa dạng, hoặc số cách chia quà để đạt được giá trị kỳ vọng trên.

Input

• Dòng đầu tiên gồm số nguyên ~T~ (~1 \le T \le 2~).

• Dòng thứ hai gồm hai số nguyên ~N~ và ~M~ (~1 \le N \le 2 \cdot 10^5, 1 \le M \le 10^9~) — số loại quà và số túi quà của ông già Noel.

• Dòng thứ ba gồm ~N~ số nguyên ~a_1, a_2, \dots, a_N~ (~1 \le a_i \le 10^6~) — số hộp quà của mỗi loại quà.

Output

• Nếu ~T = 1~, in ra một số nguyên là giá trị kỳ vọng lớn nhất của độ đa dạng, lấy dư cho ~998\,244\,353~.

• Nếu ~T = 2~, in ra một số nguyên là số cách chia quà để độ đa dạng đạt giá trị kỳ vọng lớn nhất, lấy dư cho ~998\,244\,353~.

Scoring

Sample Input 1

1
2 4
3 4

Sample Output 1

698771049

Sample Input 2

2
2 4
3 4

Sample Output 2

4

Notes

Hai ví dụ trên chỉ khác nhau ở giá trị của ~T~. Cách chia để độ đa dạng đạt được giá trị kỳ vọng lớn nhất là cho ~3~ túi chứa các loại quà ~1~ và ~2~, túi còn lại chỉ chứa loại quà ~2~.

• Giá trị kỳ vọng lớn nhất là ~\frac{19}{10} \equiv 698\,771\,049 \pmod {998\,244\,353}~.

• Có tổng cộng ~4~ cách chia quà như trên (mỗi vị trí của túi chỉ chứa loại quà ~2~ tương ứng với một cách chia).