题目内容

在一个古老的王国里，有一位聪明的数学家杨辉，他被人们尊称为“杨辉老师”。他发明了一种特殊的排列方式，被后人称为“杨辉三角”。这种排列方式可以将二项式系数按照特定的方式排列在三角形中。

在这个王国里，塔子哥是一位年轻有为的数学家。他对杨辉老师的杨辉三角非常感兴趣，经过多年的研究，他终于掌握了这个排列方式的特性，即每个数字等于上一行的左右两个数字之和。

有一天，塔子哥得到了一个整数 $n$，他想知道杨辉三角的第$n$行中有多少个奇数。他知道这个问题很简单，只需要根据杨辉三角的特性，逐行计算每个数字即可。但他想要更加高效的解决这个问题，因此他向你求助，希望你能够帮助他快速地解决这个问题。

输入描述

输入为一个整数$n$ ( $1 \leq n \leq 1000$ )，表示行数。

输出描述

输出最后一行出现了多少个奇数。

样例

输入

3

输出

2

样例说明

杨辉三角前三行为：

1

1 1

1 2 1

那么第一行有1个奇数，第二行有2个奇数，第三行有2个奇数