题目描述

    设集合Sn={1,2,3,....,n}。它的子集就是不重复地取其中任意个数所构成地集合。空集Ø={ }和Sn本身也是Sn地子集。（事实上空集是任意集合的子集。）

    若X 是Sn的子集，把X中所有数的和称为子集X的“容量”。（规定空集的容量为0）

    若X的容量为奇数，则称X为Sn的奇子集。现在我们需要对某个特定的n求出Sn的奇子集的个数。

输入格式

一行一个整数 $n$ 。

输出格式

输出一行一个正整数，表示Sn的奇子集的个数。由于这个数可能比较大，你只要输出该数模32749的结果作为答案即可。

样例

2

2

3

4

数据范围

• 对于 $30\%$ 的测试数据满足：$1≤n≤15$。
• 对于 $100\%$ 的测试数据满足：$1≤n≤10000$。