Có một chiếc hộp được dán nhãn với mỗi số nguyên từ $1$ đến $N$. Ngoài ra, với mỗi số nguyên từ $1$ đến $N$, có $M$ quả bóng được dán nhãn với số nguyên đó.
$NM$ quả bóng này được xáo trộn và sau đó phân phối vào $N$ chiếc hộp, với đúng $M$ quả bóng được đặt vào mỗi hộp.
Có $\frac{(NM)!}{(M!)^N}$ cách khả thi để đặt các quả bóng (nếu tất cả các quả bóng được coi là có thể phân biệt), và tất cả các cách sắp xếp này đều có xác suất xảy ra như nhau.
Bạn sẽ thực hiện các thao tác trên những chiếc hộp và quả bóng này. Một thao tác bao gồm các bước sau:
- Chọn một chiếc hộp và đi đến trước chiếc hộp đó.
- Nếu không có quả bóng nào trong hộp đó, kết thúc thao tác.
- Chọn bất kỳ một quả bóng nào từ hộp đó và loại bỏ nó ra ngoài hộp.
- Cuối cùng, đi đến trước chiếc hộp có nhãn trùng với nhãn của quả bóng vừa bị loại bỏ gần nhất, và quay lại bước 2.
Định nghĩa điểm số của bạn là số lượng thao tác cần thiết cho đến khi tất cả $NM$ quả bóng đã bị loại bỏ. Bạn muốn tối thiểu hóa điểm số này.
Hãy tìm giá trị kỳ vọng của điểm số khi bạn hành động tối ưu, theo modulo $998244353$.
Dữ liệu vào
Dòng đầu tiên chứa $N$ và $M$ theo thứ tự đó, cách nhau bởi dấu cách. ($1 \le N \le 10^5$, $1 \le M \le 100$)
Dữ liệu ra
In ra câu trả lời.
Ví dụ
Dữ liệu vào 1
2 2
Dữ liệu ra 1
166374060
Dữ liệu vào 2
3 1
Dữ liệu ra 2
831870296
Dữ liệu vào 3
100000 100
Dữ liệu ra 3
402978825
Ghi chú
Đối với ví dụ đầu tiên, các cách sắp xếp bóng có thể xảy ra và các cách vận hành tối ưu tương ứng như sau:
Đặt hai quả bóng dán nhãn 1 vào hộp 1, và hai quả bóng dán nhãn 2 vào hộp 2. (Xác suất $1/6$)
- Trong thao tác đầu tiên, đi đến trước hộp 1. Từ đó, lấy ra một quả bóng dán nhãn 1 và đi đến trước hộp 1. Sau đó lấy ra một quả bóng dán nhãn 1 khác và đi đến trước hộp 1 lần nữa. Tại thời điểm này, hộp 1 trống, nên kết thúc thao tác.
- Trong thao tác thứ hai, đi đến trước hộp 2. Từ đó, lấy ra một quả bóng dán nhãn 2 và đi đến trước hộp 2. Sau đó lấy ra một quả bóng dán nhãn 2 khác và đi đến trước hộp 2 lần nữa. Tại thời điểm này, hộp 2 trống, nên kết thúc thao tác.
- Trong trường hợp này, điểm số tối thiểu đạt được là 2.
Đặt một quả bóng dán nhãn 1 và một quả bóng dán nhãn 2 vào mỗi hộp 1 và hộp 2. (Xác suất $2/3$)
- Trong thao tác đầu tiên, đi đến trước hộp 1. Từ đó, lấy ra một quả bóng dán nhãn 1 và đi đến trước hộp 1. Sau đó lấy ra một quả bóng dán nhãn 2 và đi đến trước hộp 2. Sau đó lấy ra một quả bóng dán nhãn 2 và đi đến trước hộp 2. Sau đó lấy ra một quả bóng dán nhãn 1 và đi đến trước hộp 1. Tại thời điểm này, hộp 1 trống, nên kết thúc thao tác.
- Trong trường hợp này, điểm số tối thiểu đạt được là 1.
Đặt hai quả bóng dán nhãn 2 vào hộp 1, và hai quả bóng dán nhãn 1 vào hộp 2. (Xác suất $1/6$)
- Trong thao tác đầu tiên, đi đến trước hộp 1. Từ đó, lấy ra một quả bóng dán nhãn 2 và đi đến trước hộp 2. Sau đó lấy ra một quả bóng dán nhãn 1 và đi đến trước hộp 1. Sau đó lấy ra một quả bóng dán nhãn 2 và đi đến trước hộp 2. Sau đó lấy ra một quả bóng dán nhãn 1 và đi đến trước hộp 1. Tại thời điểm này, hộp 1 trống, nên kết thúc thao tác.
- Trong trường hợp này, điểm số tối thiểu đạt được là 1.
Tóm lại, điểm số tối thiểu là 2 với xác suất $1/6$, và điểm số tối thiểu là 1 với xác suất $5/6$, vì vậy giá trị kỳ vọng của điểm số tổng thể là $7/6$. Do đó, xuất ra $166374060$, đại diện cho giá trị này theo modulo $998244353$.
Có thể chứng minh rằng giá trị kỳ vọng cần tìm luôn là một số hữu tỉ. Ngoài ra, dưới các ràng buộc của bài toán này, nếu giá trị kỳ vọng được viết dưới dạng phân số tối giản $\frac{y}{x}$, thì đảm bảo rằng $x$ không chia hết cho $998244353$.
Trong trường hợp này, tồn tại một số nguyên duy nhất $z$ trong khoảng từ $0$ đến $998244352$ (bao gồm cả hai đầu), thỏa mãn $xz \equiv y \pmod{998244353}$. Hãy xuất ra $z$ này.