The Big Dance

Bessie and the herd — $N$ cows in all ($1 \le N \le 2{,}200$), conveniently numbered $1 \ldots N$ — have gone to a dance where plenty of bulls are waiting as partners. It is called the odd cow out dance because of the way partners are chosen.

The cows stand in a single line in numerical order, and a middle point is chosen. The middle either splits the line exactly in half, or, when the number of cows is odd, it is placed so that the front group holds exactly one more cow than the back group.

Each group is then handled as follows:

• If the group has exactly two cows, both are chosen to dance with bulls.
• If the group has exactly one cow, she is sent home with a consolation rose.
• If the group has more than two cows, the same splitting rule is applied to it again, repeatedly, until every group holds one or two cows.

Whenever a pair is chosen to dance, their two ID numbers are multiplied together and the product is added to a global sum.

Given the number of cows $N$, compute the global sum after every eligible pair has danced.

Worked example for $N = 11$ (cows numbered $1 \ldots 11$):

1     2     3     4     5     6  |  7     8     9     10     11

    1     2     3  |  4     5     6

        1     2  |  3
                1  2        => 1*2=2 added to sum -> sum=2
                3           => sent home with rose

        4     5  |  6
                4  5        => 4*5=20 added to sum -> sum=22
                6           => sent home with rose

    7     8     9  | 10    11

        7     8  |  9
                7  8        => 7*8=56 added to sum -> sum=78
                9           => sent home with rose
        10    11            => 10*11=110 added to sum -> sum=188

The global sum for this dance is $188$.

One line containing a single integer $N$ ($1 \le N \le 2{,}200$).

One line containing a single integer: the global sum computed as described above.