/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
1, 2, 3, 4 の 4 頂点からなる完全グラフがあります。
あなたはこれから 6 つの各辺に重みを割り当てます。いずれの重みも正整数であり、6 つの重みの和がちょうど K になるように割り当てます。
より形式的には、\sum_{1\leq i<j\leq 4}x_{i,j}=K となる正整数 x_{i,j} \ (1\leq i<j\leq 4) を選び、i, j を結ぶ辺に重み x_{i,j} を割り当てます。
この辺に重みをつけたグラフ G の 全ての頂点を通る サイクルにおける辺の重みの総和の最小値を f(G) とします。 考えうる全ての G に対する f(G) の総和を 998244353 で割ったあまりを求めて下さい。
完全グラフとは
任意の異なる 2 頂点間に辺があるグラフを完全グラフと言います。
制約
- 6 \le K \le 5000
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
K
出力
答えを出力せよ。
入力例 1
7
出力例 1
24
6 つの辺のうち 1 つの重みが 2 であり、それ以外の辺の重みが 1 であるようなグラフが考えられます。 そのようなグラフ G は 6 通りあり、いずれの場合も f(G)=4 であるため、答えは 24 です。
入力例 2
2026
出力例 2
513760748
Score : 400 points
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.
Sample Input 1
7
Sample Output 1
24
The possible graphs are the ones where one of the six edges has weight 2 and the other edges have weight 1. There are six such graphs G, and we have f(G)=4 for each of them, so the answer is 24.
Sample Input 2
2026
Sample Output 2
513760748