#include #define BOARD_SIZE 8 #define MOD 1000000007 int board[BOARD_SIZE + 1][BOARD_SIZE + 1], num_layouts; void layout(int i, int j, int king) { board[i][j] = king; if (!king || (king && !(board[i - 1][j] || board[i][j - 1]))) { if (i == BOARD_SIZE && j == BOARD_SIZE) { if (++num_layouts == MOD) num_layouts = 0; } else { int nexti = i + (j / BOARD_SIZE); int nextj = 1 + (j % BOARD_SIZE); layout(nexti, nextj, 0); layout(nexti, nextj, 1); } } } int main(void) { layout(1, 1, 0); layout(1, 1, 1); printf("%d\n", num_layouts); }