说明

相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。

该游戏是在一块铜板装置上，有三根杆(编号$A、B、C$)，在$A$杆自下而上、由大到小按顺序放置$n$个金盘(如下图)。

• 游戏的目标：把$A$杆上的金盘全部移到$C$杆上，并仍保持原有顺序叠好。
• 操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于$A、B、C$任一杆上。

请问$n$个金盘的情况下，需要最少移动多少次？

输入格式

输入一个整数$n$代表金盘的数量

输出格式

一个整数，代表$n$个金盘的移动次数

样例

3

7

121

2658455991569831745807614120560689151

501

6546781215792283740026379393655198304433284092086129578966582736192267592809349109766540184651808314301773368255120142018434513091770786106657055178751

数据范围

$1 \leqslant n\leqslant 5000$