题目描述

相信平面几何对你来说一定不陌生。现在，请你拿出纸和笔来，尝试解决这样一道几何题。

给定一个整数g，在第一象限内画出所有端点分别在两个坐标轴上，且端点横纵坐标和为g的所有线段，请你尝试计算出这些线段与坐标轴围成的图形中包含的三角形个数。

例如，当g为3时，你将画出(0, 2)(1, 0)与(0, 1)(2, 0)两条线段，这些线段与坐标轴围成的图形如图所示。图中共有4个三角形，其顶点坐标分别为(0, 2)(0, 0)(1, 0)、(0, 2)(0, 1)(2/3, 2/3)、(1, 0)(0, 0)(2, 0)、(2/3, 2/3)(1, 0)(2, 0)。

输入格式

共一行，为一个整数g，含义如题目描述所述。 ​

输出格式

共一行，表示你所求解的三角形数量。 由于这个数量可能会很大，你只需要输出数量对 $998244353$ 取模后的值。

样例

2

1

3

4

【说明】

样例解释请见问题描述部分。

4

10

【说明】

样例解释如下图所示。

5

20

996

164674490

999996

608861885

999999996

536236838

数据范围与提示

对于 $10\%$ 的数据：$g≤5$。

对于 $20\%$ 的数据：$g≤10$。

对于 $40\%$ 的数据：$g≤10^3$。

对于 $70\%$ 的数据：$g≤10^6$。

对于 $100\%$ 的数据：$2≤g≤10^9$。

可能会用到的公式：$(n+1)^3-n^3=3n^2+3n+1$