题目描述

一根笔直的木棍，长度为 N。现在要把它恰好切割成四段，要求每段的长度均为正整数，且四段可以围成一个矩形。

问：有多少种满足要求的切割方案？答案可能很大，你只需要输出其 mod 998244353 的值。

注：切割时，木棍损耗忽略不计。

输入格式

一个整数 N。

输出格式

一个整数，表示答案。

样例1输入

6

样例1输出

6

样例1解释

一共有 10 种切割方案：

• (1, 1, 1 ,3);
• (1, 1, 2, 2);
• (1, 1, 3, 1);
• (1, 2, 1, 2);
• (1, 2, 2, 1);
• (1, 3, 1, 1);
• (2, 1, 1, 2);
• (2, 1, 2, 1);
• (2, 2, 1, 1);
• (3, 1, 1, 1)。

但以下 4 种切割方案得到的 4 段小木棍无法围成矩形：

• (1, 1, 1, 3),
• (1, 1, 3, 1),
• (1, 3, 1, 1),
• (3, 1, 1, 1)。

样例2输入

123456

样例2输出

185179

数据范围

100% 的数据：1 ≤ N ≤ $10^7$