410656: GYM104069 H Harada Football Clube

Lucas Harada is one of the biggest fans of SPFC (St. Petersburg Football Club) and also of combinatorics problems, so why not join both in a problem? A football formation tactic is a distribution of players as goalkeeper, defense, midfield, or attack in which there is exactly one goalkeeper, at least one in defense, at least one in midfield, and at least one in the attack.

For example, in a traditional soccer team with 11 players, some examples of tactical formation are 1-4-4-2, 1-5-4-1, and 1-3-4-3. Note that it doesn't matter which players are in each position, only the amount. Now Harada is wondering if a football team had $$$N$$$ players, how many tactical formations would be possible?

The input consists of a single integer $$$N$$$ $$$(4 \leq N \leq 10^6)$$$, the number of players on the team.

The output consists of a single integer, the number of possible tactical formations of a team with $$$N$$$ players.

4

1

6

6

11

36

1000000

499997500003

On the second testcase the possible formations are: 1-1-1-3; 1-2-2-1; 1-1-3-1; 1-2-1-2; 1-3-1-1; 1-1-2-2.