题意：

有一个图片说明 大小的棋盘，你需要在棋盘上面放图片说明 个点，问使得第一行，第一列，最后一行，最后一列都有点的方案数，答案对图片说明 取模。

解法一（暴力搜索，不可AC）：

直接枚举矩阵每个点是否放点，然后判断是否符合要求再统计答案。
具体的，我们递归地用图片说明 表示当前考虑第图片说明 个点，当前已经放了图片说明 个点，依次统计答案。
代码： 

class Solution {
public:
    const int mod=1e9+7;
    int n,m,k;
    int ans;
    int vis[4];//vis[0]表示第一行点的数量，vis[1]表示第一列点的数量,vis[2]表示最后一行点的数量，vis[3]表示最后一列点的数量
    void dfs(int i,int j){
        if(i>n*m){
            if(j!=k)return;
            //已经考虑完所有的点了
            if(vis[0]&&vis[1]&&vis[2]&&vis[3])ans=(ans+1)%mod;
            return;
        }
        if(j>k)return;//如果放的点比总的点数还要多，直接返回
        //计算当前坐标
        int x=(i-1)/m+1;
        int y=i-(x-1)*m;
        //放点
        if(x==1)vis[0]++;
        if(y==1)vis[1]++;
        if(x==n)vis[2]++;
        if(y==m)vis[3]++;
        dfs(i+1,j+1);
        if(x==1)vis[0]--;
        if(y==1)vis[1]--;
        if(x==n)vis[2]--;
        if(y==m)vis[3]--;
        dfs(i+1,j);
    }
    int solve(int n, int m, int k) {
        this->n=n,this->m=m,this->k=k;
        this->ans=0;
        memset(vis,0,sizeof vis);
        dfs(1,0);
        return ans;
    }
};

时间复杂度：图片说明 ，棋盘总共有图片说明 个点，每个点有两种方案，故时间复杂度为图片说明
空间复杂度：图片说明 ，棋盘大小为图片说明 ，需要递归的深度也为这么多，故空间复杂度为图片说明

解法二（状态压缩动态规划）：

我们设图片说明 表示前图片说明 行，总共用了图片说明 个点，第一行，第一列，最后一行，最后一列是否有点的状态为图片说明 （图片说明为一个4位的二进制数，第0、1、2、3位分别表示第一行，第一列，最后一行，最后一列，其中二进制位为1表示有点，为0表示没有点 ）的方案数。
为了更直观起见，我们以下都用二进制串来表示图片说明 ，并且第0、1、2、3位是从左到右的。
首先考虑第1行：
第一行一个点也不放，显然方案数为1
图片说明

第一行有点，第一列和最后一列都没有点，如下图所示：

在个格子放个点，
第一行、第一列有点，最后一列没有点，如下图所示：

在个格子放个点，
第一行、最后一列有点，第一列没有点，如下图所示：

在个格子放个点，
第一行、第一列，最后一列都有点，如下图所示：

在个格子放个点，
接着我们考虑第图片说明 行：

我们考虑枚举状态图片说明

1. 当图片说明 表示的第一列，最后一列都为1时：
    分为三种情况：
        （1）当前行的上面第一列、最后一列都没有点，如下图所示：
                
                那么我们考虑当前行总共放个点，第一列和最后一列必须各放一个点，在个格子放个点，即：
                    
        （2）当前行上面第一列没有点、最后一列有点，如下图所示：
                
                那么我们考虑当前行总共放个点，我们当前行第一列一定要放一个点，剩下的位置随便放，在个格子放个点，即：
                    
        （2）同理，当前行上面最后一列没有点，第一列有点，可得：
                    
综上所述，当表示的第一列，最后一列都有点时：
图片说明

类似的，我们可以得出下面几种情况。
2. 当表示的第一列为1，最后一列为0时：
图片说明
3. 当s表示的第一列为0，最后一列为1时：
图片说明
4. 当s表示的第一列，最后一列都为0时：
图片说明
由于最后一行状态我们只需要答案表示的状态，故我们直接考虑答案如何求解：
图片说明
代码： 
class Solution {
public:
    const int mod=1e9+7;
    int f[31][1001][1<<4];
    int C[31][31];//杨辉三角，C[i][j]表示组合数
    inline int calc(int n,int m){//计算组合数
        if(n<0||m<0)return 0;
        if(m>n)return 0;
        return C[n][m];
    }
    inline int get_state(bool a,bool b,bool c,bool d){//第0、1、2、3位是否是1的状态
        int x=0;
        if(a)x|=1;
        if(b)x|=1<<1;
        if(c)x|=1<<2;
        if(d)x|=1<<3;
        return x;
    }
    inline bool check_state(int x,int k){//判断状态x的第k位是否是1
        return x&(1<<k);
    }
    int solve(int n, int m, int k) {
        memset(f,0,sizeof f);
        memset(C,0,sizeof C);//多测清空
        C[0][0]=1;
        for(int i=1;i<=30;i++){
            C[i][0]=C[i-1][0];
            for(int j=1;j<=i;j++){
                C[i][j]=(C[i-1][j]+C[i-1][j-1])%mod;//递推求解杨辉三角
            }
        }
        f[1][0][0]=1;//第一行，放了0个点，第一行，第一列，最后一行，最后一列都没有点的方案数为1
        for(int j=1;j<=k;j++){
            //设置第一行边界状态
            f[1][j][get_state(true,false,false,false)]=calc(m-2,j);
            f[1][j][get_state(true,true,false,false)]=calc(m-2,j-1);
            f[1][j][get_state(true,false,false,true)]=calc(m-2,j-1);
            f[1][j][get_state(true,true,false,true)]=calc(m-2,j-2);
        }
        for(int i=2;i<n;i++){
            //第2~n-1行状态
            for(int j=0;j<=k;j++){
                for(int c=0;c<=j&&c<=m;c++){
                    for(int s=0;s<(1<<4);s++){
                        if(check_state(s,2))continue;//第2到n-1行所表示的状态s最后一行肯定没有点
                        if(check_state(s,1)&&check_state(s,3)){
                            //第一列，最后一列的点都唯一在当前行
                            f[i][j][s]+=1ll*f[i-1][j-c][s^(1<<1)^(1<<3)]*calc(m-2,c-2)%mod;
                            f[i][j][s]%=mod;
                            //上面没有第一列的点，那么当前行在第一列一定要放点
                            f[i][j][s]+=1ll*f[i-1][j-c][s^(1<<1)]*calc(m-1,c-1)%mod;
                            f[i][j][s]%=mod;
                            //上面没有最后一列的点，那么当前行最后一列一定要放点
                            f[i][j][s]+=1ll*f[i-1][j-c][s^(1<<3)]*calc(m-1,c-1)%mod;
                            f[i][j][s]%=mod;
                            //上面第一列和最后一列都有点，这一行随便放
                            f[i][j][s]+=1ll*f[i-1][j-c][s]*calc(m,c)%mod;
                            f[i][j][s]%=mod;
                        }else if(check_state(s,1)){
                            //上面没有第一列的点，那么当前行所在的第一列一定要放点
                            f[i][j][s]+=1ll*f[i-1][j-c][s^(1<<1)]*calc(m-2,c-1)%mod;
                            f[i][j][s]%=mod;
                            //上面有第一列的点，那么随便放
                            f[i][j][s]+=1ll*f[i-1][j-c][s]*calc(m-1,c)%mod;
                            f[i][j][s]%=mod;
                        }else if(check_state(s,3)){
                            //上面没有最后一列的点，那么当前行所在的最后一列一定要放点
                            f[i][j][s]+=1ll*f[i-1][j-c][s^(1<<3)]*calc(m-2,c-1)%mod;
                            f[i][j][s]%=mod;
                            //上面有最后一列的点，那么随便放
                            f[i][j][s]+=1ll*f[i-1][j-c][s]*calc(m-1,c)%mod;
                            f[i][j][s]%=mod;
                        }else{
                            //第一列和最后一列都没有，那么在m-2范围内随便放
                            f[i][j][s]+=1ll*f[i-1][j-c][s]*calc(m-2,c)%mod;
                            f[i][j][s]%=mod;
                        }
                    }
                }
            }
        }
        int s=get_state(true,true,true,true);
        int ans=0;
        for(int j=1;j<k;j++){
            //按照上面同理进行讨论
            ans+=1ll*f[n-1][k-j][s^(1<<1)^(1<<3)^(1<<2)]*calc(m-2,j-2)%mod;
            ans%=mod;
            ans+=1ll*f[n-1][k-j][s^(1<<1)^(1<<2)]*calc(m-1,j-1)%mod;
            ans%=mod;
            ans+=1ll*f[n-1][k-j][s^(1<<3)^(1<<2)]*calc(m-1,j-1)%mod;
            ans%=mod;
            ans+=1ll*f[n-1][k-j][s^(1<<2)]*calc(m,j)%mod;
            ans%=mod;
        }
        return ans;
    }
};

时间复杂度：图片说明，数组最后一维的大小为，可视为常数，故状态图片说明 的复杂度为图片说明 的，每次转移需要枚举当前行选了多少个，代价是图片说明 的，故总的时间复杂度为图片说明
空间复杂度：图片说明 ，存储状态图片说明 需要图片说明 级别的内存，存储杨辉三角需要图片说明 级别的内存，故总的空间复杂度为图片说明