Hot Ones - the show with hot questions and even hotter wings...
people participated in the latest iteration of Hot Ones at Amplitude. There were
sauces and everyone got a raffle ticket for every sauce
they successfully tried, and the winner will get all of the Hot Ones sauces to enjoy!
The sauces each have unique integral kilo-Scoville heat unit values from
to
. Each individual will eat the sauces in increasing order of kilo-Scoville heat units.
Unfortunately, due to the popularity of Hot Ones, some individuals were not able to try out every sauce. For every possible subset of sauces, exactly one person tried that exact subset of sauces.
Because no one wanted to be the first to go grab the ice cream, everyone waited until the very end of the event to go eat ice cream. The number of litres of ice cream a person ate was exactly equal to their maximum spice jump.
The maximum spice jump of a person is equal to the maximum increase in kilo-Scoville heat units between consecutive sauces. We
assume for simplicity that everyone started out trying a kilo-Scoville sauce.
The workplace team wants to ensure that they purchase enough ice cream for everyone, but not so much that they have melted ice cream leftover to deal with.
Constraints
Input Specification
The first and only line of input contains a single integer, .
Output Specification
Let be the number of litres of ice cream the workplace team must buy. Output the remainder when
is divided by
998244353
.
Sample Input 1
3
Sample Output 1
12
Sample Explanation 1
There are 7 people who participated. Their maximum spice levels are as follows:
- Person 1 tried only sauce
and had a maximum spice jump of
.
- Person 2 tried only sauce
and had a maximum spice jump of
.
- Person 3 tried sauces
and
and had a maximum spice jump of
.
- Person 4 tried only sauce
and had a maximum spice jump of
.
- Person 5 tried sauces
and
and had a maximum spice jump of
.
- Person 6 tried sauces
and
and had a maximum spice jump of
.
- Person 7 tried sauces
,
, and
, and had a maximum spice jump of
.
In total, they eat litres of ice cream.
Sample Input 2
28
Sample Output 2
367691381
Sample Explanation 2
We can show that the number of litres of ice cream eaten in this scenario is . The remainder when
is divided by
is
.
Comments