题目描述

对于一个排列A = (a[1], a[2], ... , a[n])，定义价值c[i] 为a[1]至a[i-1]中小于a[i]的数的个数。 即c[i] = |{a[j] |j < i, a[j] < a[i]}|。定义A的价值为Sum(c[1]+c[2]+...+c[n])。 给定n，求1至n的全排列中所有排列的价值之和。

输入格式

输入一行包含一个整数n。 对于40%的评测用例，n≤20； 对于70%的评测用例，n≤5000； 对于所有评测用例，2≤n≤1000000。

输出格式

输出一行包含一个整数表示答案。 由于所有排列的价值之和可能很大，请输出这个数除以998244353的余数。

输入样例

样例1：
3

样例2：
2022

输出样例

样例1：
9

样例2：
593300958

数据范围与提示

1至3构成的所有排列的价值如下: (1, 2, 3) : 0 + 1 + 2 = 3 ； (1, 3, 2) : 0 + 1 + 1 = 2 ； (2, 1, 3) : 0 + 0 + 2 = 2 ； (2, 3, 1) : 0 + 1 + 0 = 1 ； (3, 1, 2) : 0 + 0 + 1 = 1 ； (3, 2, 1) : 0 + 0 + 0 = 0 ； 故总和为3 + 2 + 2 + 1 + 1 = 9。