牛客IOI周赛16-普及组-C答题卡

这题我在周赛时没做出来，是参考楼上各位大神的思路才想明白的，我想把我的思路分享给大家。
答题卡是 的，要求出所有的使横竖答题卡对称的涂写方案。
首先，应该看清楚题面给出的条件，横竖答题卡都只能填一个答案，并且横竖答题卡是要对称的。所以横答题卡某一行的答案确定之后，对应的竖答题卡的某一列的答案也就确定了，并且交于这两个答案的行和列也已经确定了，不明白？看图解释：
以n = 3可以看到，当将第一行的答案放在第一列的时候，剩下的就是求的答题卡规模为 的所有方案,当第一行的答案放在第二列的时候，剩下的就是求答题卡规模为 的所有方案，同理将第一行的答案放在第三列也是一样的。而n = 4的所有情况也是跟n = 3类似。
所以我们可以得出这样的结论：
在棋盘规模为 的情况下，除去将第一行的答案放在第一列之外（这种情况是转化为求(n - 1) * (n - 1)的所有方案数），剩余的情况有 种，并且这 情况都是一样的，都是求棋盘规模为 的所有方案数。


则我们可以得出这样的公式：

之后代码就很容易写啦，大家自己写一写吧。
我是算法小白，代码有缺陷欢迎指正。
代码：

#include <iostream>
using namespace std;

const long long mod = 1000000007;

int main(){
    int n;
    cin >> n;
    if(n == 0) { cout << 0 << endl; return 0; }
    if(n == 1) { cout << 1 << endl; return 0; }
    if(n == 2) { cout << 2 << endl; return 0; }
    long long ans1 = 1;
    long long ans2 = 2;
    long long sum;
    for (int i = 3; i <= n; ++i)
    {
        sum = (ans2 + (i - 1) * ans1) % mod;
        ans1 = ans2;
        ans2 = sum;    
    }
    cout << sum << endl;
    return 0;
}