Background

在火星上，土拨鼠博博发现了一种神奇的细菌......

Description

在第k时刻，每一只神奇的细菌都会在第(k+1)时刻分裂成一模一样的两个。在第0时刻仅有1个细菌，请你计算一下，在第n时刻有几个细菌。

Format

Input

一个正整数，n

Output

在第n时刻有几个细菌。

Samples

1

2

67

147573952589676412928

Limitation

• 对于10%的数据，$0≤n≤63$
• 对于30%的数据，$0≤n≤10^2$
• 对于60%的数据，$0≤n≤10^4$
• 对于90%的数据，$0≤n≤10^5$
• 对于最后一个测试点，$n=10^6+7$，评测时间30s，其余测试点1s