410227: GYM103987 C Make it in a Line

Memory Limit:512 MB Time Limit:1 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

C. Make it in a Linetime limit per test1 secondmemory limit per test512 megabytesinputstandard inputoutputstandard output

The game Tic-Tac-toe is played by two people taking turns on a $$$3 \times 3$$$ board, with the person winning the game when his first getting a whole horizontal or vertical or diagonal line filled with his tokens. It's easy to find that there are only $$$8$$$ ways of putting tokens to win the game (only considering the tokens in the key line).

All $$$8$$$ winning ways are shown in the picture below.

Today, Walk_alone is bored with playing the 2D Tic-Tac-Toe with Salix Leaf! He thinks the board is too small and the winning ways are too monotonous. So they decide to make a larger chess board and add a brand new dimension to the game! Now this game seems more interesting:

In a 3D $$$n \times n \times n$$$ cube, two people put their tokens by turn, and the first one whose tokens fill one horizontal or vertical or diagonal line of the cube wins the game. For instance, some winning ways in a 3D $$$4 \times 4 \times 4$$$ cube are shown in the picture below.

He is too lazy to do any calculation, so he wants you to tell him the number of ways to put the tokens in a line.

Input

The first and the only line of the input contains an integer $$$n\ (2 \leq n \leq 1000)$$$.

Output

Print only one number representing the number of ways to put the tokens in a line.

Scoring

The problem contains $$$20$$$ test cases. You can get $$$5$$$ points for each passed test case.

ExamplesInput
2
Output
28
Input
3
Output
49
Input
4
Output
76

加入题单

上一题 下一题 算法标签: