题目描述

数学成绩出来，某T折戟沉沙，涉险及格。而宁静折取桂冠。然而为了E文测验，宁静带了个九连环回学校供她欣赏。

宁静：这个就是经典的九连环啦！九连环的每个环互相制约，只有第一环能够自由上下。要想下/上第$\red{n}$个环，就必须满足两个条件：

一、第$\red{n-1}$个环在架上；

二、第$\red{n-1}$个环前面的环全部不在架上。

这样一来的话如果我想解第一个环的话就是这样，两个环的话我先也可以直接下。三个环的时候就这样：

$\red{1}$、下$\red{1}$环 　$\red{2}$、下$\red{3}$环

$\red{3}$、上$\red{1}$环 　$\red{4}$、下$\red{2}$环

$\red{5}$、下$\red{1}$环

编程：对于给定的$\red{n}$个环，编程输出出拆卸的次数。

输入格式

一个正整数$\red{n(1≤n≤800)}$,要拆卸的环。

输出格式

一个整数$\red{M}$，所需的步数

样例

输入样例

20

输出样例

699050