Universal Cup Judging System

Universal Cup

Time Limit: 2.0 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

There are $U + T + P + C$ cards. Among them, $U$ cards have a picture of a unicorn on the front, $T$ cards have a tiger, $P$ cards have a panda, and $C$ cards have a cat. Initially, all cards are placed face down, and it is impossible to distinguish which picture is on each card.

You will play a game using these cards. The game consists of several turns. In each turn, you choose to perform either Operation A or Operation B:

  • Operation A: Choose one of the face-down cards uniformly at random and flip it face up. If the drawn card shows a unicorn, tiger, or panda, you proceed to the next turn and the game continues. The flipped card remains face up. If the drawn card shows a cat, the game ends immediately. In this case, your score will be $0$.
  • Operation B: End the game immediately. Let $u$ be the number of face-up cards showing a unicorn, and $t$ be the number of face-up cards showing a tiger. Your score will be $2u + t$.

Find the expected score when following the optimal strategy to maximize your expected score, modulo $998244353$.

Note on Expected Value Modulo $998244353$

It can be proven that the expected value in this problem is always a rational number. Additionally, under the constraints of this problem, when the expected value is represented as an irreducible fraction $\frac{x}{y}$, it is guaranteed that $y$ is not divisible by $998244353$. Therefore, there uniquely exists an integer $z$ ($0 \le z < 998244353$) such that $y \cdot z \equiv x \pmod{998244353}$. You should output this $z$.

Input

The input is given from Standard Input in the following format:

$$U \quad T \quad P \quad C$$

  • All input values are integers.
  • $1 \le U, T, P, C \le 10^6$

Output

Print the answer on a single line.

Examples

Input 1

1 1 1 1

Output 1

166374060

Input 2

2 7 1 8

Output 2

300941313

Input 3

20 26 2 14

Output 3

631490021

Note

  • In the first example, here is one possible progression of the game (note that this is not necessarily the optimal strategy):
    • If you perform Operation B on the $1$-st turn, your score will be $0$ and the game ends. Suppose you perform Operation A instead, and the flipped card shows a unicorn.
    • In this state, if you perform Operation B on the $2$-nd turn, your score will be $2$ and the game ends. Suppose you perform Operation A instead, and the flipped card shows a panda.
    • In this state, if you perform Operation B on the $3$-rd turn, your score will be $2$ and the game ends. Suppose you perform Operation A instead, and the flipped card shows a cat. Because a cat was drawn, your score becomes $0$ and the game ends.
  • If you follow the optimal strategy, it can be shown that the expected score is $\frac{7}{6}$.

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1415EditorialOpen题解jianglyView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.