#include #include #define BOARD_SIZE 8 #define COLUMN_LAYOUTS 55 // Must be (BOARD_SIZE + 2)-th Fibonacci number. #define MOD 1000000007 int L[BOARD_SIZE][COLUMN_LAYOUTS], D[1 << BOARD_SIZE][1 << BOARD_SIZE]; int main(void) { int i, j, k, l, M, n, c, cc, sz, ans; /* Build adjacency (compatibility) matrix between column configurations. */ k = -1; for (i = 0; i < (1 << BOARD_SIZE); i++) { if ((i & (i >> 1)) == 0) { ++k; l = -1; for (j = 0; j < (1 << BOARD_SIZE); j++) { if ((j & (j >> 1)) == 0) { ++l; if ((i & j) == 0) { D[k][l] = D[l][k] = 1; } } } } } /* Number of all possible layouts in a column. */ sz = k + 1; assert(sz == COLUMN_LAYOUTS); /* Base cases. */ for (c = 0; c < COLUMN_LAYOUTS; c++) L[0][c] = 1; /* Recurrence. */ for (n = 1; n < BOARD_SIZE; n++) { for (c = 0; c < COLUMN_LAYOUTS; c++) { L[n][c] = 0; for (cc = 0; cc < COLUMN_LAYOUTS; cc++) { if (D[c][cc]) { L[n][c] = (L[n][c] + L[n - 1][cc]) % MOD; } } } } /* Answer. */ ans = 0; for (c = 0; c < COLUMN_LAYOUTS; c++) ans = (ans + L[BOARD_SIZE - 1][c]) % MOD; printf("%d\n", ans); return 0; }