Tyvj 兩周年慶典要到了，Sam 想為 Tyvj 做一個(gè)大蛋糕。蛋糕俯視圖是一個(gè) N×M 的矩形，它被劃分成 N×M 個(gè)邊長(zhǎng)為 1×1 的小正方形區(qū)域（可以把蛋糕當(dāng)成 N 行 M 列的矩陣）。蛋糕很快做好了，但光禿禿的蛋糕肯定不好看！所以，Sam 要在蛋糕的上表面涂抹果醬。果醬有三種，分別是紅果醬、綠果醬、藍(lán)果醬，三種果醬的編號(hào)分別為 1,2,3。為了保證蛋糕的視覺效果，Admin 下達(dá)了死命令：相鄰的區(qū)域嚴(yán)禁使用同種果醬。但 Sam 在接到這條命令之前，已經(jīng)涂好了蛋糕第 KK 行的果醬，且無法修改。

現(xiàn)在 Sam 想知道：能令 Admin 滿意的涂果醬方案有多少種。請(qǐng)輸出方案數(shù) mod10⁶ 。若不存在滿足條件的方案，請(qǐng)輸出 0。

輸入共三行。

第一行：N,M；

第二行：K；

第三行：M 個(gè)整數(shù)，表示第 K 行的方案。

字母的詳細(xì)含義見題目描述，其他參見樣例。

樣例說明：

數(shù)據(jù)范圍與提示：

對(duì)于 30% 的數(shù)據(jù)，1≤N×M≤20；

對(duì)于 60% 的數(shù)據(jù)，1≤N≤1000,1≤M≤3；

對(duì)于 100% 的數(shù)據(jù)，1≤N≤10000,1≤M≤5。

信息學(xué)一本通 動(dòng)態(tài)規(guī)劃