Migrated from Lutece 2588 投硬币

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

瑄有一个爱好是收集硬币，他已经收集了 $20$ 年的硬币，谁也不知道他现在到底有多少枚硬币。他最喜欢的游戏就是「抛硬币」，每次投掷硬币都会让他心情愉快。这个游戏想必大家也都玩过，将一枚硬币抛到地面上，结果要么正面朝上要么反面朝上。

瑄长大了，不再满足于仅仅投掷一枚硬币。今天他从他的无尽的硬币库存中取出了 $N$ 个硬币，并在无尽的地面上依次投掷取出的每一枚硬币，投掷好的硬币瑄会把他们按照投掷顺序依次排成一排，他认为如果存在连续排列的三个硬币都是正面或者都是反面，那么这个排列是丑陋的，反之这个排列就是美观的。他想知道这 $N$ 个硬币来排列，有多少个丑陋的排列。虽然瑄数学很优秀，但他只想单纯的玩游戏，并不想将宝贵的时间花在思考这个问题上面，作为瑄好朋友的你，可以帮助他找出丑陋的排列的个数吗？

Input

一个正整数 $N\ (1 \leq N \leq 10000)$，表示硬币的个数。

Output

输出一个整数，即丑陋排列的个数。

Samples

4

6

Resources

2021 UESTC ICPC Training for Dynamic Programming