Problem Statement

There is a complete graph with four vertices numbered $1, 2, 3, 4$.

You will now assign weights to each of the six edges. Each weight should be a positive integer, and the sum of the six weights should be exactly $K$. More formally, you choose positive integers $x_{i,j} \ (1\leq i<j\leq 4)$ such that $\sum_{1\leq i<j\leq 4}x_{i,j}=K$, and assign weight $x_{i,j}$ to the edge connecting $i$ and $j$.

For this weighted graph $G$, let $f(G)$ be the minimum sum of edge weights in a cycle that passes through all vertices. Find the sum, modulo $998244353$, of $f(G)$ over all possible $G$.

What is a complete graph? A complete graph is a graph with an edge between every pair of two distinct vertices.

Constraints

• $6 \le K \le 5000$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

K

Output

Output the answer.