Gahee and the Tunnel

Interview

Time limit1sMemory limit512 MB

Summary

Count the length-s strings over 7 snack colors that contain red, orange, yellow, green, blue, navy, purple in that order as a subsequence, modulo 998244353.

Level: Medium5 of 10
Topics: Dynamic programming, Combinatorics, String
Solved: No attempts yet

Problem

Gahee's older brother bought her a tunnel-shaped nose work toy. Gahee wants to crawl inside it and find the sweet potato snacks her brother hid. The toy has $s$ spots where snacks can be hidden. The spots are numbered in order from 1 to $s$ .

The toy follows these rules.

Gahee starts at spot 1.
After visiting spot $i$ , she visits spot $i+1$ . So with $s$ spots, she visits spots 1, 2, 3, ..., $s$ in that order.
When she visits a spot with a snack, she may eat the sweet potato snack or skip it.
She cannot visit the same spot twice.
She can eat at most 7 snacks.

There are 7 kinds of sweet potato snacks: red, orange, yellow, green, blue, navy, and purple. How many ways are there to place sweet potato snacks in the $s$ spots so that the following conditions hold? Two placements are different if at least one spot has a different snack kind.

Each spot must get exactly one snack, chosen from the 7 kinds.
Gahee must be able to follow the rules above and eat snacks in the order red, orange, yellow, green, blue, navy, purple. At least one such way must exist.

Input

The first line contains $s$ .

Output

Print the answer modulo $998\,244\,353$ .

Constraints

$1 \le s \le 50\,299$
There are more than $s$ sweet potato snacks of each of the 7 kinds.

Examples3

Example 1
Input
```
7
```
Expected output
```
1
```
Example 2
Input
```
8
```
Expected output
```
49
```
Example 3
Input
```
33336
```
Expected output
```
471076917
```