← 返回题目列表

AtCoder · arc212_a

A. 四个 TSP

中文机器翻译题面 查看原题

分数: 400 点

问题陈述

有一个完整的图,有四个顶点编号 1, 2, 3, 4.

您现在将为六个边中的每一个分配权重。每个权重应为正整数,并且六个权重之和应恰好为 K.
更正式地说,您选择正整数 x_{i,j} \ (1\leq i<j\leq 4) 这样 \sum_{1\leq i<j\leq 4}x_{i,j}=K,并分配权重 x_{i,j} 到边缘连接 i 和 j.

对于此加权图 G,让 f(G) 是一个循环中边权重的最小总和, 穿过所有顶点。 求总和,取模 998244353,属于 f(G) 总体而言 G.

什么是完整图?

完整图是在每对两个不同顶点之间具有边的图。

约束

  • 6 \le K \le 5000
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

K

输出

输出答案。


示例输入 1

7

示例输出 1

24

可能的图是六个边之一具有权重的图 2 且其他边有权重 1。 这样的图有六张 G,我们有 f(G)=4 对于他们每个人,所以答案是 24.


示例输入 2

2026

示例输出 2

513760748