410656: GYM104069 H Harada Football Clube
Description
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?
InputThe input consists of a single integer $$$N$$$ $$$(4 \leq N \leq 10^6)$$$, the number of players on the team.
OutputThe output consists of a single integer, the number of possible tactical formations of a team with $$$N$$$ players.
ExamplesInput4Output
1Input
6Output
6Input
11Output
36Input
1000000Output
499997500003Note
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.