### 问题描述 小蓝喜欢研究棋盘上棋子的摆放。棋盘可以看作是一个 $n\times n$ 的网格图，棋子可以放到格子中。现在有一种叫做“车”的棋子，车可以攻击棋盘上和它处于同一行或者同一列的棋子。也就是说，在任意一行中只能存在小于等于一个车，任意一列也只能存在小于等于一个车。我们假定车是有颜色的，那么请问 $n$ 个颜色相同的车放在 $n\times n$ 棋盘上且车不能相互攻击的方案数是多少？$n$ 个颜色互不相同的车放在 $n\times n$ 棋盘上且车不能相互攻击的方案数是多少？ 若方案 $A$ 和方案 $B$ 中存在至少一辆车的摆放位置不同，或者虽然 $n$ 辆车的摆放位置相同但是存在一个位置摆放的车的颜色是不一样的，则方案 $A$ 和方案 $B$ 被认为是不同的方案。 方案数可能会很大，请输出方案数对 $10^9+7$ 取模后的结果。 ### 输入格式 一个正整数 $n$，含义如题目所述。 ### 输出格式 一行 $2$ 个整数，中间用 $1$ 个空格分开。第一个数字表示颜色相同时的方案数，第二个数字表示颜色互不相同时的方案数。 ### 样例输入 ```text 2 ``` ### 样例输出 ```text 2 4 ``` ### 说明 对于 20% 的数据，$n\leq 5$。 对于 50% 的数据，$n\leq 1000$。 对于 100% 的数据，$n\leq 10^6$。