Long long long long long long long long long long time ago, there's a lovely kingdom named "Chess". There's King, Queen, Knight, Castle, Bishop, ...etc. Just like the modern game "chess".
A king definitely have not only one castle or knight. But no one says that a king shouldn't have two or more queens (same as queen, a queen is able to have two or more kings). Now in this kingdom, the king has N queens.
However, all the queens want to get the title "King's favorite", if one is uglier than the other one (which is judged by the king), then just win by manner. If one is more rude than the other one, then just win by skills. But if a queen loses on everything...... then just let them disappear or die "accidentally"...HEHEHE..... The king soon realized that, for the safety of all of his lovely queens, he must make them cannot see each other.
Now, the king ask you, the mighty programming knight, for a mission. They want to find out how many possibilities that the queens won't launch a war in the palace.
Warning! Do not just look up the answer table! You are supposed to solve this problem by recursive. Otherwise you will regret it!
The input contains exactly one number N.
1 <= N <= 14.
Output only one number ── the total amount of states that queens are placed in the palace and mission isn't failed.
Remember to print a '\n' at the end of the output.