题目描述

经典汉诺塔有三根柱子。现在柱子的数量变成了 $4$ 根：$n$ 个大小不同的圆盘一开始都套在 $1$ 号柱上，按从上到下由小到大摆放。每次只能移动一个圆盘，而且任何时候大盘子都不能压在小盘子上。

把全部 $n$ 个圆盘都搬到 $4$ 号柱上，最少需要移动多少次？

输入格式

一行一个整数 $n$。

输出格式

一行一个整数，表示最少移动次数。

输入输出样例 #1

输入 #1

5

输出 #1

13

说明

数据范围

• 对于 $100\%$ 的数据，$0\le n\le 1000$。