题目描述

小S面前有一个全是由1构成的字符串，被称为全1序列，差不多长成这样11111111...。你可以合并任意相邻的两个1（这样就变成2了），从而形成一个新的序列。对于给定的一个全1序列(也就是给你长度)，请计算根据以上方法，可以构成多少种不同的序列。

注意：可以合并多次，并且只能合并1

输入输出格式

输入格式

这里包括多组测试数据，每组测试数据包含一个正整数N，代表全1序列的长度。

输出格式

对于每组测试数据，输出一个整数，代表由题目中所给定的全1序列所能形成的新序列的数量。

样例 1

样例输入

1
3
5

样例输出

1
3
8

限制

时间限制1s，内存限制128KB

提示

样例解释

• 对于数据1 只能生成一个字符串1
• 对于数据2 能生成三个字符串，111,12,21
• 对于数据3 能生成八个字符串，11111,2111,1211,1121,1112,221,212,122

数据范围

对于100%的数据，\(1 \leq N \leq 200\)