J. Eternal Feather II
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

翼なんて無くてかまわない 即使没有翅膀也没关系

だから届けて ふたりへ 因而我们两个人能够到达

永遠（とわ）に変わらぬ あの空 永恒不变的 那片天空

在音羽的教堂见过优子最后一面之后，夕毅然转头离开音羽教堂。一曲 ever forever 响起，ef 的故事就此落幕。夕不愿忘记与优子的回忆，但他仍然需要一个人坚强的活下去。

圣诞节这天，他发现了一个长度为 $$$n$$$ 的，由 $$$\{\mathtt{y},\mathtt{u},\mathtt{k},\mathtt{o}\}$$$ 为字符集构成的字符串。他想要求出这样的串的个数，使得这个串不包含一个子串，这个子串经过重新排列之后可以构成 $$$\mathtt{yuuko}$$$。

夕是建筑领域专家，但他并不会算法竞赛。你能帮助他吗？

由于答案可能很大，你只需要输出答案对 $$$998 \, 244 \, 353$$$ 取模的结果。

Input

一个数 $$$n$$$（$$$1\leq n\leq 10^{18}$$$），代表字符串长度。

Output

一个数，表示答案对 $$$998 \, 244 \, 353$$$ 取模的结果。

Examples
Input
2
Output
16
Input
5
Output
964