depou

Consider a depot like the one in the picture below. You can notice that there's an entry line, on which n wagons numbered from 1 to n, in the order of entrance, go in.
The wagons go into the depot and then go out in a certain order on the exit line.

 

Task

Given the number of wagons, determine the number of distinct wagon arrangements on the exit line.

Input Data

Input file depou.in contains a single line with a positive integer n representing the number of wagons.

Output Data

Output file depou.out will contain a single line with a positive integer representing the number of distinct wagon arrangements on the exit line.

Constraints
  • 1 <= n <= 150
    •

    Examples

    depou.in

    depou.out

    Explanation

    3

    		5

    The 5 possibilities are:
    1 2 3
    (wagon 1 enters the depot and then exits;     wagon 2 enters the depot and then exits, wagon 3 enters the depot and then exits)
    1 3 2
    (    wagon 1 enters the depot and then exits; wagon 2 enters the depot, wagon 3 enters the depot, wagon 3 exits the depot and then wagon 2 exits the depot)
    2 1 3
    (wagon 1 enters the depot; wagon 2 enters the depot, wagon 2 exits de depot, wagon 1 exits the depot, chart 3 enters the depot and then wagon 3 exits the depot)
    2 3 1
    (wagon 1 enters the depot; wagon 2 enters the depot and then wagon 2 exits the depot, wagon 3 enters the depot, wagon 3 exits the depot and then wagon 1 exits the depot)
    3 2 1
    (wagon 1 enters the depot; wagon 2 enters the depot, wagon 3 enters the depot, and then wagon 3 exits the depot, wagon 2 exits the depot, wagon 1 exits the depot)

     

    Time limit: 0.1 seconds/test

    prof. Marinel Serban
    Computer Science High School "Grigore Moisil" Iasi
    marinel_serban@yahoo.com