Description
Sasha enjoys playing patiences. Last days he played very interesting patience on a rectangular grid 14 * 4. The rules of this patience are very simple. He takes a standard 52-card deck (without jokers), extracts all aces and lays them in the first column of the grid. Cell (1, 1) contains ace of diamonds, (1, 2) -- ace of hearts, (1, 3) -- ace of clubs and (1, 4) contains ace of spades. Then Sasha shuffles the rest of the deck and lays all cards in a sequental order by row, leaving column 2 empty, so all the columns from 3 to 14 are covered by cards.
After having laid all cards in such a manner, he is allowed to make moves. The move is determined by selection of a free cell. This free cell is to be covered by the card defined by the contents of the left adjacent cell. The covering card must have the same suit and the next value (order of values is: Ace 2 3 4 5 6 7 8 9 10 Jack Queen King). For example, if the cell (6, 3) contains the Queen of Spades, and the cell (7, 3) is empty, selecting cell (7, 3) will move the King of Spades to (7, 3) (and leave empty the cell where the King of Spades was before the move). If the left neighbour of the free cell contains a King or is empty, the move selecting this free cell is disabled.
The goal is to make each row ordered (i.e. columns from 1 to 13 must contain cards from Ace to King, and the column 14 must be empty). If all free cells follow Kings or empty cells, and the cards are not ordered, Sasha is considered a loser (in the classic version of this patience, the rest of the deck may be shuffled two times again leaving ordered cards on their positions, but Sasha is very experienced and often wins without additional shuffling).
Now Sasha wants to know some things about this patience. Imagine the position where three suits are already ordered, and the remaining suit is ordered partially. It is known that there are less than n highest cards that are not ordered. So only n rightmost columns may contain unordered cards. For example, if n = 3, columns from 1 to 11 are ordered, and columns from 12 to 14 contain Queen, King and empty cell in an arbitrary order. Sasha wants to determine how many of such positions for a given n have a winning strategy. For example, if n = 3, there is only one position that does not allow him to win: . . . [King] [empty] [Queen]. All other positions have a winning strategy:
1. . . . [Queen] [King] [empty] is already a goal position
2. . . . [Queen] [empty] [King] allows to move King adjacent to the Queen.
3. . . . [empty] [Queen] [King] becomes previous position after moving the Queen after the Jack.
4. . . . [empty] [King] [Queen] becomes goal position by moving the Queen after the Jack.
5. . . . [King] [Queen] [empty] becomes position 3 after moving the King to the free cell.
So for n = 3 the answer is 5.
Write the program that will get the answer for an arbitrary n from 1 to 13.
Input
Input file consists of only one integer number n.
Output
Write to the output file the answer to the task -- the number of positions with less than n highest cards not ordered in the remaining suit that have a winning strategy.
Sample Input
4
Sample Output
14
