219. How Many Subsets

Core1000 ms256 MBSolved by 0%

A set has n distinct elements. Print how many subsets it has, counting both the empty set and the set itself.

Think about it one element at a time. For each element you make an independent choice: in or out. That is the shape of every backtracking problem you will meet, and here you only have to count the leaves rather than list them.

Read the constraint. At n = 62 there are more subsets than you could ever generate, so this is a counting problem rather than a generating one.

Constraints - `0 ≤ n ≤ 62`

Input

A single line containing one integer n.

Output

Print one integer, the number of subsets.

Input3

Output8

Noteis a set of three, which has eight subsets

Input0

Output1

Noteis the empty set, which still has one subset: itself

Hint 1Approach

Hint 2Approach

Hint 3Pseudocode

Hint 4Full solution