public class Main{
    public static int count = 0;
    public static void main(String[] args) {
        int n = 3;
        char[][] grid = {{'.','.','#'},{'.','.','#'},{'.','.','.'}};
        boolean[][] used = new boolean[n][n];
        int stuNum = 7;
        dfs(grid, 0, 0, used, 0, stuNum);
        System.out.println(count);
    }
    public static void dfs(char[][] grid, int i, int j, boolean[][] used, int curNum, int stuNum){
        if(!inArea(grid, i, j) || used[i][j])
            return;
        used[i][j] = true;
        if(grid[i][j] != '.')
            return;
        if(i == grid.length-1 && (curNum+1) == stuNum){
            count++;
            return;
        }
        dfs(grid, i, j+1, used, curNum+1, stuNum);
        dfs(grid, i+1, j, used, curNum+1, stuNum);
        dfs(grid, i, j-1, used, curNum+1, stuNum);
        dfs(grid, i-1, j, used, curNum+1, stuNum);
        used[i][j] = false;
    }
    public static boolean  inArea(char[][] grid, int i, int j){
        return i>=0 && i < grid.length && j >= 0 && j < grid[0].length;
    }
  }