Có $U + T + P + C$ lá bài. Trong số đó, $U$ lá bài có hình kỳ lân ở mặt trước, $T$ lá bài có hình hổ, $P$ lá bài có hình gấu trúc, và $C$ lá bài có hình mèo. Ban đầu, tất cả các lá bài đều được đặt úp xuống, và không thể phân biệt được hình nào nằm trên mỗi lá bài.
Bạn sẽ chơi một trò chơi sử dụng những lá bài này. Trò chơi bao gồm một số lượt. Trong mỗi lượt, bạn chọn thực hiện Thao tác A hoặc Thao tác B:
- Thao tác A: Chọn ngẫu nhiên đồng đều một trong các lá bài đang úp và lật ngửa nó lên. Nếu lá bài rút được có hình kỳ lân, hổ hoặc gấu trúc, bạn chuyển sang lượt tiếp theo và trò chơi tiếp tục. Lá bài đã lật vẫn giữ nguyên trạng thái ngửa. Nếu lá bài rút được có hình mèo, trò chơi kết thúc ngay lập tức. Trong trường hợp này, điểm của bạn sẽ là $0$.
- Thao tác B: Kết thúc trò chơi ngay lập tức. Gọi $u$ là số lá bài đang ngửa có hình kỳ lân, và $t$ là số lá bài đang ngửa có hình hổ. Điểm của bạn sẽ là $2u + t$.
Hãy tìm điểm kỳ vọng khi tuân theo chiến lược tối ưu để cực đại hóa điểm kỳ vọng của bạn, theo modulo $998244353$.
Lưu ý về Giá trị Kỳ vọng Modulo $998244353$
Có thể chứng minh rằng giá trị kỳ vọng trong bài toán này 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, khi giá trị kỳ vọng được biểu diễn dưới dạng phân số tối giản $\frac{x}{y}$, đảm bảo rằng $y$ không chia hết cho $998244353$. Do đó, tồn tại duy nhất một số nguyên $z$ ($0 \le z < 998244353$) sao cho $y \cdot z \equiv x \pmod{998244353}$. Bạn cần in ra số $z$ này.
Dữ liệu vào
Dữ liệu vào được cung cấp từ Đầu vào Chuẩn theo định dạng sau:
$$U \quad T \quad P \quad C$$
- Tất cả các giá trị đầu vào đều là số nguyên.
- $1 \le U, T, P, C \le 10^6$
Dữ liệu ra
In câu trả lời trên một dòng duy nhất.
Ví dụ
Đầu vào 1
1 1 1 1
Đầu ra 1
166374060
Đầu vào 2
2 7 1 8
Đầu ra 2
300941313
Đầu vào 3
20 26 2 14
Đầu ra 3
631490021
Ghi chú
- Trong ví dụ đầu tiên, dưới đây là một diễn biến có thể xảy ra của trò chơi (lưu ý rằng đây không nhất thiết là chiến lược tối ưu):
- Nếu bạn thực hiện Thao tác B ở lượt thứ $1$, điểm của bạn sẽ là $0$ và trò chơi kết thúc. Giả sử bạn thực hiện Thao tác A thay vào đó, và lá bài được lật có hình kỳ lân.
- Ở trạng thái này, nếu bạn thực hiện Thao tác B ở lượt thứ $2$, điểm của bạn sẽ là $2$ và trò chơi kết thúc. Giả sử bạn thực hiện Thao tác A thay vào đó, và lá bài được lật có hình gấu trúc.
- Ở trạng thái này, nếu bạn thực hiện Thao tác B ở lượt thứ $3$, điểm của bạn sẽ là $2$ và trò chơi kết thúc. Giả sử bạn thực hiện Thao tác A thay vào đó, và lá bài được lật có hình mèo. Vì rút phải mèo nên điểm của bạn trở thành $0$ và trò chơi kết thúc.
- Nếu bạn tuân theo chiến lược tối ưu, có thể chứng minh rằng điểm kỳ vọng là $\frac{7}{6}$.