Stone Merging Sum

We are given a row of stone piles. For any sequence of piles with n piles having a₁, a₂, …, a_n stones (with each a_i \(\ge 1\) and \(\sum_{i=1}^n a_i = S\)), we define a merging process as follows:

• In one move, you can merge two adjacent piles with stone counts \(x\) and \(y\) into one pile with \(x+y\) stones, at a cost of \(xy\).
• You continue merging until only one pile remains.

It can be proved that no matter how you merge, the minimal total cost is always \[ f(a_1,\ldots,a_n)=\sum_{1\le i<j\le n}a_i a_j = \frac{S^2-\sum_{i=1}^n a_i^2}{2}. \]

Your task is: Given an integer \(S\) (the total number of stones), consider all compositions of \(S\) into a sequence of positive integers (each composition \((a_1, a_2,\ldots,a_n)\) satisfies \(\sum_{i=1}^n a_i=S\)). For each such composition, let \(f(a_1,\ldots,a_n)\) be its minimal merging cost. Compute

[ \sum_{a_1+\cdots+a_n=S} f(a_1,\ldots,a_n) \pmod{998244353}. ]

Note: A composition is an ordered partition; for example, when \(S=3\), the compositions are \([3], [1,2], [2,1], [1,1,1]\), with respective costs \(0, 1\times2, 2\times1, (1\cdot1+1\cdot1+1\cdot1)=3\). The answer for \(S=3\) is \(0+2+2+3=7\).

inputFormat

The input consists of a single integer \(S\) (\(1 \le S \le \) some reasonable limit).

Note that each composition of \(S\) is taken into account (for \(S\ge2\), the single element composition has merging cost 0).

outputFormat

Output a single integer, which is the sum of the minimal merging costs for all compositions of \(S\), taken modulo \(998244353\).

sample

1

0