406237: GYM102319 G Jonathan and Jason at the Jowling Jalley I

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

Description

G. Jonathan and Jason at the Jowling Jalley Itime limit per test1 secondmemory limit per test256 megabytesinputstandard inputoutputstandard output

Jonathan and Jason are huge weeaboos who spend all their time at home watching anime and reading light novels. But one day, the Google restaurant "Charlie's" was closed to all employees due to an invasion of wild UBC interns, so Jonathan and Jason spontaneously decided to go bowling. Unfortunately, the wild UBC interns got to the Google bowling alley "Gooowling Galley" first, and all the lanes were out of order, although actually they were out of order for several months already and the entire building was just a front for Baidu's secret invasion, but that's a problem for another time...

Basically Jonathan and Jason somehow ended up at a mysterious and sketchy location in Jupiter, the bowling alley "Jowling Jalley". The Martians are very skilled bowlers, so instead of using a mere 10 pins arranged in a triangle, with sides of length 4, the Martians use up to 210 pins arranged in a triangle, with sides of length 4 ≤ n ≤ 20. Jonathan is very bad at bowling, so he forced Jason to play the "easy mode" variation with him, which is only popular among little children who watch cartoons.

In the "easy mode" variation, a hi-tech forcefield made out of op-amps and shafts under fatigue loading physically prevents the ball from knocking down any pins other than the first one, at the tip of the triangle. However, that first pin can still knock down the pins behind it, which can knock down more pins behind it, like a pile of Panago's. Basically, due to the hi-tech physics involved (it involves calculations of the von Mises stress using the Coulomb–Mohr criterion), the forcefield mysteriously warps causality in such a way that a pin can only be knocked down if both pins in front of it are also knocked down.

For example, after rolling the bowling ball, the first three positions below are possible, where o is an upright pin and x is a knocked-down pin. However, the last three positions are impossible, because at least one of the pins in front of pin X are not knocked down.


____o____ ____x____ ____x____ ____o____ ____x____ ____x____
___o_o___ ___x_o___ ___x_x___ ___X_o___ ___x_o___ ___x_o___
__o_o_o__ __x_o_o__ __x_x_o__ __o_o_o__ __o_X_o__ __x_o_o__
_o_o_o_o_ _o_o_o_o_ _x_o_o_o_ _o_o_o_o_ _o_o_o_o_ _x_X_o_o_

After every roll, a JeleVision (a telly made of jelly) displays a mysterious and sketchy animated video of a cartoon bowling ball knocking over cartoon bowling pins. This made Jonathan and Jason very excited because they are huge weeaboos. But they were also UBC students in the past, so naturally they wondered, how many animated videos did Jmazon (the company that owns the bowling alley "Jowling Jalley") have to produce? Jmazon has to produce exactly one animated video for every possible position that the pins can end up in, after Jonathan or Jason rolls the bowling ball once.

Input

The only line of the input is the integer n, the side length of the triangle of pins (4 ≤ n ≤ 20).

Output

Print the integer x, the number of possible positions after one roll in the Jowling Jalley, with the "easy mode" variation.

ExampleInput
4
Output
42

加入题单

上一题 下一题 算法标签: