java-藍橋杯試題格子刷油漆，求思路

藍橋杯試題格子刷油漆，求思路

X國的一段古城牆的頂端可以看成 2*N個格子組成的矩形（如圖1所示），現需要把這些格子刷上保護漆。

你可以從任意一個格子刷起，刷完一格，可以移動到和它相鄰的格子（對角相鄰也算數），但不能移動到較遠的格子（因為油漆未干不能踩！）

比如：a d b c e f 就是合格的刷漆順序。

c e f d a b 是另一種合適的方案。

當已知 N 時，求總的方案數。當N較大時，結果會迅速增大，請把結果對 1000000007 (十億零七) 取模。

輸入數據為一個正整數（不大於1000）

輸出數據為一個整數。

例如：
用戶輸入：
2
程序應該輸出：
24

再例如：
用戶輸入：
3
程序應該輸出：
96

再例如：
用戶輸入：
22
程序應該輸出：
359635897

資源約定：
峰值內存消耗（含虛擬機） < 64M
CPU消耗 < 2000ms

最佳回答：

這個問題要反過來想不合理的情況。其實很簡單，只需要排除一種情況，就是有一列的兩個都被刷了，而前面還有未刷的，這樣就回不來了。比如例子中，如果c,d都被刷了，而a,b有一個或者兩個都未刷，這時候如果已經移動到了e,f列中，就無法返回a,b了，就完成不了了。也就是說，如果前面有未刷的，那麼就不能允許有一列的兩格都被刷。