考点:dp+思维
刚开始写的时候读不懂题意，不太明白如何下手，看了样例的图片后有了一些灵感，发现好像对称，索性找了一下规律。
发现我们可以把这个问题分为两种情况，第一种就是选左上角的格子，这样的话第一行第一列都不能涂，就是有dp[n-1]种；
如果不选左上角的格子，第一行还可以选n-1个格子，必须一次选两个对称的，这样就剩了dp[i-2]种可以选；
递推式为dp[i] = dp[i-1]+(i-1)*dp[i-2]; 
import java.math.*;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;
import java.util.*;
public class Main {
    public static void main(String args[])throws IOException
    {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        in.nextToken();
        int n = (int)in.nval;
        long dp[] = new long[1000000];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] =4 ;
        dp[4] = 10;
        long mod = 1000000007;
        for(int i=5;i<=n;i++)
            dp[i] = (dp[i-1]+(i-1)*dp[i-2])%mod;
        out.println(dp[n]%mod);
        out.flush();
    }
                  }