棋盘上的車

【题目描述】

在$n*n(n≤20)$的方格棋盘上放置$n$个車，求使它们不能互相攻击的方案总数。

【输入格式】

一行一个正整数$n$。

【输出格式】

一行一个正整数，即方案总数。

【样例输入】

3

【样例输出】

6

【来源】

周伟，《状态压缩》，引例