Simple Arithmetic 3(binary)

2 secs 1024 MB
Rute

注意:この問題文には日本語版がありません。

Problem Statement


This year,There are teams entried World BaseBall Contest.
This World BaseBall contest is Tournament, and only 1 team will be Champion.
How many games will it be before a Champion is decided?
However, all matches shall end in a win or a loss, and no tie shall be considered.
This answer can be large, so output the remainder divided by .

Constraints


is Integer

・This site doesn't have a partial point system, but I'll just show partial points.
・Full Mark is Point
・(Constraints 1)   ( Point)
・(Constraints 2)   ( Point)
・(Constraints 3) No additional restrictions.  ( Point)

Input


Output


Please output "How many games will it be before a Champion is decided".

Sample Case


Input
2
Output
3

There are teams Entried.
On the First Round, There are match, teams will be defeated.
On the Second Round(and it is Final Round), teams will be defeated and Champion is decided.
So, The answer is , Please output .

Sample Case


Input
10000
Output
905611804

This answer can be large, so output the remainder divided by .And it contained Constraints 2 Cases.

提出


Go (1.14)