Background

xixisuper 曾经在一个上午之内整理出了 6000 词的莫比乌斯反演论文。

这跟这个题没有任何关系，他只是想炫耀一下，这题真的不需要用到任何关于莫比乌斯反演的科技。

他要是骗人的话 cyh 是小狗。

cyh：“柠檬的，不敢说话了 WC”

Description

给定全集 $U$ 的大小 $|U|$，求^[1]

$$\sum_{A\subseteq U}\sum_{B\subseteq U}\sum_{x\subseteq A}\sum_{y\subseteq B}\left[x\oplus y\subseteq A\oplus B\right] $$

答案对 $998244353$ 取模。

Constraints and Subtasks

本题共 10 个测试点，各测试点等分

对于全部测试点，满足 $n\le 10^{14}$。

其中，部分测试点有特殊性质：

测试点	数据范围
$1$	$n\le 10$
$2\sim 5$	$n\le 10^6$
$6\sim 10$	$n\le 10^{14}$

---

Input

输入内容从标准输入给出，格式如下：

$ \boxed{\begin{aligned} {\quad} & n_1 {\quad} \end{aligned}} $

Output

输出一行一个整数，为和式的结果模 $998244353$ 的值。

Samples

8

5764801

---

1. 式子中的 $\oplus$ 为集合的标准差，即 $S\oplus T=\{x\mid x\in S\cup T\land x\notin S\cap T\}$，它的标准形式写作 $S\triangle T$，也可以参考 Set 的注释。 ↩︎