Hide

Problem J
Fortune Telling

What you see is only a moment $\dots $

In an attempt to earn enough money to support her activities, the Great Witch of Calamity has taken up a new side job: fortune telling! Her setup involves two decks of cards colored blue and black, respectively. The blue cards are numbered $1$ to $X$ from top to bottom, and the black cards are numbered similarly from $1$ to $Y$.

She will put all these cards into the Pile of Fate via the following operations. She may do them in any order, and as many times as she wishes:

  • If she has less than two cards in her hand, she may draw one card from either the deck of blue cards, or the deck of black cards, as long as the deck she draws from is nonempty.

  • If she has at least one card in her hand, she may place any of these cards into the Pile of Fate.

Both her hand and the Pile of Fate start out empty.

When she is done, she will then read her client’s fortune from the arrangement of cards in the Pile of Fate. Because every arrangement leads to a different fortune, she wonders how many arrangements are possible. Can you answer this?

Input Format

The only line of input contains two space-separated integers $X$ and $Y$: the number of blue and the number of black cards, respectively. It holds that $0 \leq X, Y \leq 10^5$ and $1 \leq X + Y$.

Output Format

Output one integer: the number of possible fortunes (i.e. final arrangements of cards). Since this may be very large, output the answer modulo $998\, 244\, 353$.

Explanation

To help explain the first sample test case, let the $i$th blue card be labeled $A_ i$, and the $i$th black card be labeled $B_ i$.

For the first test case, there are $60$ possible final arrangements. One of them, from bottom to top, is

\[ A_1, B_2, A_2, B_1, B_3 \]

She can achieve this via the following set of operations:

  • Pick up $A_1$, then pick up $B_1$, then discard $A_1$.

  • Pick up and discard $B_2$, and $A_2$. Note that $B_1$ is still in her hand.

  • Discard $B_1$.

  • Pick up and discard $B_3$.

Note that there may be other sequences of operations that can obtain this arrangement. Despite this, we only count this arrangement once.

For the second test case, remember to reduce the answer by the given modulo.

Sample Input 1 Sample Output 1
2 3
60
Sample Input 2 Sample Output 2
31 42
233671175
CPU Time limit 3 seconds
Memory limit 1024 MB
Statistics Show
Author
Dan Alden Baterisna
Source NUS Competitive Programming
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in