題目連結：
題目大意：
在一個二維平面上，每走一步為一個單位。而現規定每一步只能往上、往右、往左走，且不能走到前面走過的點上。
現給定一正整數 Ｎ （０ ＜ Ｎ ≦ １０, ０００），代表走 Ｎ 步。求走 Ｎ 步的方法數，並將結果取 １２, ３４５ 的餘數。
範例輸入：
【範例輸入一】
2
【範例輸入二】
1
範例輸出：
【範例輸出一】
7
【範例輸出二】
3
解題思維：
一樣是典型的ＤＰ（動態規劃）的題型。
由於走 Ｎ 步的時候，向左走、向右走的走法是不會相鄰在一起的（不然就會走到走過的點）。因此我們能得出：
「向左走」後，下一步只能接「向左走」或是「向上走」。
「向上走」後，下一步可以接著任意走法。
「向右走」後，下一步只能接「向上走」或是「向右走」。
因此我們可以得出一ＤＰ陣列 Ｗ ｉｊ ， ｉ 代表走了 ｉ 步， ｊ 代表以 ｊ 為結尾的走法（ ０ 代表「向左」、 １ 代表「向上」、 ２ 代表「向右」），並按照以上規律得：
Ｗ ｉ０ ＝ Ｗ (ｉ - １)０ ＋ Ｗ (ｉ - １)１
Ｗ ｉ１ ＝ Ｗ (ｉ - １)０ ＋ Ｗ (ｉ - １)１ ＋ Ｗ (ｉ - １)２
Ｗ ｉ２ ＝ Ｗ (ｉ - １)１ ＋ Ｗ (ｉ - １)２
然後，在作運算時，就各自取 12345 的餘數。即可求出方法數 ＝
（Ｗ Ｎ０ ＋ Ｗ Ｎ１ ＋ Ｗ Ｎ２） Mod 12345
