该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Description

对于一棵随机生成的\(n\)个节点的有根二叉树（所有互不同构的形态等概率出现），它的叶子节点期望个数是多少？
为了方便解题，你可以在提示中找到判断有根二叉树同构的代码。

Format

Input

每个测试点包含至多\(6324\)组测试数据，请处理至文件结束。
每组数据仅包含一行一个整数\(n(1<=n<=10^9)\)。

Output

对于每组数据，可以证明，答案一定为有理数，设其最简分数表示为\(p/q\)，那么请输出一行一个整数\(x(0<=x<998244353)\)，满足\(qx\) \(mod\) \(998244353=p\)，这样的\(x\)必然是存在且唯一的。

Sample 1

Input

3
6324

Output

598946613
757584352

Limitation

1s, 1GB for each test case.

Hint

\(n=3\)时真正的答案为\(1.2\)，\(n=6324\)时真正的答案约为\(1581.3750296513\)。

C++ Code

//T1,T2分别表示两棵树的根节点。
bool check(node *T1,node *T2){
    if(T1==NULL||T2==NULL) return T1==NULL&&T2==NULL;
    return check(T1->leftson,T2->leftson)&&check(T1->rightson,T2->rightson);
}

Source

Vijos Original