/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 166 点
問題文
高橋君は生物学の研究室でバクテリアの増殖実験を行っています。
この実験では、特殊な培養液の中でバクテリアのコロニーが成長します。各コロニーは一定時間ごとに分裂し、元のコロニーのちょうど 2 倍のサイズを持つ新しいコロニーが生まれます。
実験開始時、培養液にはサイズ 1 のコロニーが 1 つだけ存在します。その後、以下の増殖が K 回発生します。
増殖: 現在存在するすべてのコロニーそれぞれについて、そのコロニーのサイズを 2 倍にした新しいコロニーが 1 つ生まれる。このとき、元のコロニーもそのまま残る。
つまり、増殖が起こるたびにコロニーの数が増えることになります。ただし、同じサイズのコロニーが複数存在する場合がありますが、研究ではサイズごとに分類して記録するため、同じサイズのものは 1 種類としてカウントします。
K 回の増殖が終わった後、培養液に存在するコロニーは何種類あるでしょうか？言い換えると、存在するコロニーのサイズとして現れる異なる値の個数を求めてください。
制約
- 1 \leq K \leq 10^{18}
- K は整数
入力
K
- 1 行目には、増殖の回数を表す整数 K が与えられる。
出力
K 回の増殖後に存在するコロニーの種類数（異なるサイズの個数）を 1 行で出力してください。
入力例 1
2
出力例 1
3
入力例 2
10
出力例 2
11
入力例 3
1000000000000000000
出力例 3
1000000000000000001
Score : 166 pts
Problem Statement
Takahashi is conducting a bacteria growth experiment in a biology laboratory.
In this experiment, bacteria colonies grow in a special culture medium. Each colony divides at regular intervals, and a new colony with exactly 2 times the size of the original colony is born.
At the start of the experiment, there is only 1 colony of size 1 in the culture medium. After that, the following growth occurs K times.
Growth: For each colony that currently exists, a new colony with twice the size of that colony is born. At this time, the original colony also remains.
In other words, the number of colonies increases each time growth occurs. However, there may be multiple colonies of the same size, but since the research records them classified by size, colonies of the same size are counted as 1 type.
After K growths have occurred, how many types of colonies exist in the culture medium? In other words, find the number of distinct values that appear as sizes of existing colonies.
Constraints
- 1 \leq K \leq 10^{18}
- K is an integer
Input
K
- The first line contains an integer K representing the number of growths.
Output
Output the number of types of colonies (the number of distinct sizes) after K growths in a single line.
Sample Input 1
2
Sample Output 1
3
Sample Input 2
10
Sample Output 2
11
Sample Input 3
1000000000000000000
Sample Output 3
1000000000000000001