A. Magic Computer
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Bob has a magic computer which has infinite USB ports. But there is a problem with this computer——it can only read and write the two most recently inserted USB disks.

Initially, Bob has $$$n$$$ USB disks and every USB disk has one unique file. He wants to insert all the $$$n$$$ USB disks into his computer. Since his computer is old, he must insert USB disk in the following way:

  1. Select $$$2$$$ unplugged USB disks, insert them into computer.
  2. The two USB disks inserted in the previous step will share the files with each other, which means after that both two USB disks will have all files either in the first one or in the second one.
  3. If all the $$$n$$$ USB disks are in the computer, the task is finished. Otherwise, choose one USB disk in the computer, unplug it and go to step $$$1$$$.

Bob wants to know the minimum number of $$$n$$$ such that there is a sequence of operations that ends up with at least $$$k$$$ different files in each USB disk.

Input

Only one number,$$$k$$$ ($$$2\leq k \leq 100000$$$),meaning that finally each USB disk owns at least $$$k$$$ different files.

Output

You need to output one number $$$n$$$, which means the minimum number of USB disks in module 998244353.

Examples
Input
3
Output
4
Input
5
Output
16
Input
1000
Output
510735315