409044: GYM103427 C Cards of Magic

Raiden Shogun, the ruler of Inazuma, is playing a new card game invented by her friend Yae Miko.

Pixiv ID: 93716380

The player needs to defeat a monster of health point (HP) $$$n$$$ by using magic cards properly.

Specifically, there are three kinds of magic cards:

1. Waterman: Summon the Waterman on the field and the Waterman will stay on the field forever. Each time when you cast a magic card and the Waterman has been on the field, it will reduce the monster's HP by $$$1$$$. Note that if you cast another Waterman card when the Waterman has already been on the field, nothing will happen except the monster's HP decresing by $$$1$$$;
2. Fireball: Reduce the monster's HP by $$$2$$$;
3. Copy: Copy any card casted before this card and receive a copy of the copied card.

At the beginning of each turn, the player receives a new card from one of the three kind in equal possibility of $$$\frac{1}{3}$$$. Then the player can choose to cast some magic cards in his hand one by one and the casted cards will take effect respectively. Since there is no limitation for the number of cards in hand, the player can choose to keep cards and do nothing in the turn.

The monster will be defeated if its HP becomes nonpositive. Now Raiden Shogun hopes you can calculate the expected number of turns to defeat the monster if she plays optimally to minimize the expected number of turns.

The only line contains a single integer $$$n$$$ $$$(1 \le n \le 2 \times 10^5)$$$, indicating the monster's HP.

Output a line containing an integer, indicating the expected number of turns to defeat the monster modulo $$$998\,244\,353$$$ if playing optimally.

More precisely, if the reduced fraction of the answer is $$$\frac{p}{q}$$$, what you should provide is the minimum nonnegative integer $$$r$$$ such that $$$q r \equiv p \pmod{998\,244\,353}$$$. You may safely assume that such $$$r$$$ always exists.

1

831870296

5

835978299

In the first sample case:

• If receiving a Waterman card in the first turn, just cast it and the monster will be defeated no matter receiving which kind of magic card in the next turn;
• If receiving a Fireball card in the first turn, just cast it and defeat the monster immediately;
• If receiving a Copy card in the first turn, do nothing in the following turns until receiving a Waterman card or a Fireball card. Once receiving a Waterman card, the monster will be defeated by casting the Waterman card and then casting any card in hand. Once receiving a Fireball card, the monster will be defeated by casting the Fireball card immediately.

In all, the expected number of turns to defeat the monster of HP $$$1$$$ is $$$\frac{11}{6}$$$ if playing optimally.