题目描述

汉诺塔是一个经典游戏，下面是简单的规则介绍

有三根柱子和 \(n\) 个大小不同的圆盘。

初始时，\(n\) 个圆盘都按照从大到小的顺序叠放在一号柱子上。

每次操作可以拿起一个圆盘，放到一根柱子上面，目标是将所有的圆盘从一号柱子移动到二号柱子。

在移动过程中，永远保持大盘子在下面，小盘子在上面。

\(n\) 层汉诺塔需要的操作次数是经典的问题。

Alice在汉诺塔游戏中作弊，他可以拿起一个圆盘后，另一只手可以再拿起一个圆盘，然后可以放下任意一个圆盘。简单说，Alice用两个手玩汉诺塔，手上可以寄存圆盘。

比如 \(n=2\) 的情况下，如果不作弊把两个圆盘从一号柱子转移到二号柱子，你需要把小圆盘放到三号柱子上，再把大圆盘放到二号柱子，最后把小圆盘放到二号柱子，总共三次操作。

但是Alice可以拿起两个圆盘，再把大圆盘放到二号柱子，小圆盘放到二号柱子，总共两次操作。

Alice想知道他在作弊的情况下， \(n\) 层汉诺塔需要最少多少次操作，注意一次拿起算一次操作。

因为有可能操作次数很多，你只要算出操作次数模 \(998244353\) 下的结果即可。

输入格式

输入包含一个整数 \(n\) 。

输出格式

输出一个整数表示最少操作次数模 \(998244353\) 意义下的结果。

样例 #1

样例输入 #1

3

样例输出 #1

4

样例 #2

样例输入 #2

5

样例输出 #2

10

样例 #3

样例输入 #3

114514

样例输出 #3

74477100

数据规模

对于 \(30\%\) 的数据满足 \(n \le 3\) 。

对于另外 \(30\%\) 的数据满足 \(n \le 10\) 。

对于另外 \(20\%\) 的数据满足 \(n \le 10^6\) 。

对于全部数据满足 \(1 \le n \le 10^9\) 。

下发文件

ssfz联测 下发文件