1784.
Cube Summation
时间限制 5000 ms
内存限制 150 MB
Given an integer N, consider all multi-sets of positive integers such that their sum is N.
For example, if N =3, there are three possible multi-sets {1, 1, 1}, {1, 2}, {3}.
For each multi-set calculate the cube of its size and output the sum of all these values modulo 998244353.
输入数据
输出数据
For each test case, output one line with a single integer, denoting the answer to the problem.
样例输入
复制
4
1
2
3
100000 \n
\n
\n
\n
\n
样例输出
复制
1
9
36
513842114
\n
\n
\n
\n
样例说明
For the 1st case, the only possible multi-set is {1}. So the answer is 1^3=1.
For the 2nd case, there are 2 possible multi-sets. {1, 1}, {2}. So the answer is 2^3+1^3=9.
For the 3rd case, there are 3 possible multi-sets. {1, 1, 1}, {1, 2}, {3}. So the answer is 3^3+2^3+1^3=36.