汉诺塔

题目描述

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

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

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

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

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

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

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

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

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

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

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

输入格式

输入包含一个整数 $n$ 。

输出格式

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

样例 #1

样例输入 #1

3

样例输出 #1

4

样例 #2

样例输入 #2

5

样例输出 #2

9

样例 #3

样例输入 #3

114514

样例输出 #3

609781922

提示

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

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

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

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