#269. 细菌分裂

细菌分裂

Background

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

Description

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

Format

Input

一个正整数,n

Output

在第n时刻有几个细菌。

Samples

1
2
67
147573952589676412928

Limitation

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