题目背景

辰辰和小北正在学动态规划($dp$)，他们牢牢的记住了动态规划的步骤：

1.划分阶段

2.设立状态

3.确定决策

4.状态转移

题目描述

辰辰和小北正在做一道动态规划的题，他们经过了九九八十一天的推理，得出了转移方程 $f_0=1,f_i=BC(f_{i-1})$，他们要求得 $f_n$ ，然而，当他们看到数据范围，顿时傻眼。

输入输出

输入

一行一个正整数表示 $n$。

输出

一行一个整数，答案不用取模，用 $unsigned$ $long$ $long$ 类型统计答案即可（相当于对 $2^{64}$ 取模）。

样例

0

1

1212

7545145374844559489

数据范围

对于 $20$% 的数据，$n<10^6$。

对于 $30$% 的数据，$n<10^7$。

对于 $50$% 的数据，$n<10^9$。

对于 $100$% 的数据，$n<10^{18}$

$BC$ 函数如下

unsigned long long BC(unsigned long long x){
    x=((x*998244353+1000000007)*1000000007+998244353);
    return x;
}