410278: GYM103999 G Battle of Scundu

In 10660 B.C., we will assume that, in Scundu, there has been the most epic battle to this day (because we can't prove that it didn't happen). The battle between the scundenians (the name of the people from scundu) and the invading forces was very close, so close that it was perfectly even and both sides decided to call for reinforcements. We say that the scundenians won the battle if, in every moment of the battle (since the reinforcements start to arrive), the number of scundenians engaged in battle was greater or equal to the number of invading forces engaged in battle.

Knowing the number $$$N$$$ of scundenians that come as reinforcements, the same $$$N$$$ number of invading forces that come as reinforcements and that at every second there is exactly one soldier arriving at battle (either scundenian or invader), find the number of ways the reinforcements can come so that the scundenians win The Battle of Scundu

We consider that 2 ways of the reinforcements $$$a_0 a_1 ... a_n$$$ and $$$b_0 b_1 ... b_n$$$ to come are different if at any second $$$1 \le i \le n$$$ we have $$$a_i \neq b_i$$$ (where $$$a_i$$$ and $$$b_i$$$ represent the type of the soldier that comes at the second $$$i$$$ , scundenian or invader).

You receive one integer from the console $$$N$$$ ($$$ 1 \le N \le 1.000.000$$$) , the number of soldiers each side gets as reinforcements.

You have to print one number $$$x$$$ , the number of ways the scundenians win the Battle of Scundu. Because the number can be very big, you have to output the number modulo $$$1.000.000.007$$$

• for 30 points it is guaranteed that $$$N \le 30$$$
• for another 30 points it is guaranteed that $$$N \le 1000$$$
• for the last 40 points, we have $$$N \le 1.000.000$$$

3

5

If we represent the reinforcements as a sequence $$$a_1,a_2...a_{2N} $$$ where $$$a_i = S$$$ means that at the second $$$i$$$ a scundenian arrived at the battle, while $$$a_i = I$$$ means that at the second $$$i$$$ an invader arrived at the battle, we can describe the possible ways the reinforcements can come as:

$$$SSSIII$$$

$$$SSISII$$$

$$$SSIISI$$$

$$$SISSII$$$

$$$SISISI$$$