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 .
・ 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)
Please output "How many games will it be before a Champion is decided".
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 .
This answer can be large, so output the remainder divided by .And it contained Constraints 2 Cases.