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

你可以從任意一個格子刷起，刷完一格，可以移動到和它相鄰的格子（對角相鄰也算數(shù)），但不能移動到較遠的格子（因為油漆未干不能踩?。?
比如：a  d  b  c  e  f  就是合格的刷漆順序。
c  e  f  d  a  b  是另一種合適的方案。
當已知  N  時，求總的方案數(shù)。當N較大時，結(jié)果會迅速增大，請把結(jié)果對  1000000007  (十億零七)  取模。

輸入數(shù)據(jù)為一個正整數(shù)（不大于1000） 

輸出數(shù)據(jù)為一個正整數(shù)。

零基礎(chǔ)同學(xué)可以先學(xué)習(xí)視頻課程，包含C/C++、Python、百練、藍橋杯輔導(dǎo)、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習(xí)題，還有老師答疑，點擊這里了解課程詳情

藍橋杯 動態(tài)規(guī)劃