Tnvj两周年庆典要到了，Sam为其做一个大蛋糕，蛋糕俯视图是一个N*M的矩形，它被划分成N*M个边长为1*1的小正方形区域（可以把蛋糕当成N行M列的矩阵）蛋糕很快做好的了，但光秃秃的蛋糕……肯定不好看！所以Sam要在蛋糕的上表层涂抹果酱。果酱有三种，分别是红果酱、绿果酱、蓝果酱。三种果酱的编号分别为1,2,3。为了保证蛋糕的视觉小国，Admin下达了死命令：相邻的区域严禁使用同种果酱。但Sam接到这条命令之前，已经涂好了蛋糕第K行的果酱，且无法修改。

现在Sam想知道，能令Admin满意的涂果酱方案有多少种（mod 

）。若不存在这种方案，请输出0。

输入共三行

第一行：N,M。

第二行:K。

第三行：M个整数，表示第K行的方案。

输出仅一行为可行的方案总数。

【样例说明】第一行的2 3是固定的，合理的果酱涂抹方案共三种：

【数据规模】

对于30%的数据，1≤N*M≤20。

对于60%的数据，1≤N≤1000,1≤M≤3。

对于100%的数据，1≤N≤10000,1≤M≤5。

动规专题