Description

Tyvj's second anniversary celebration is approaching, and Sam wants to make a big cake for Tyvj. The top view of the cake is an $N×M$ rectangle, divided into $N×M$ small square regions of size $1×1$ (you can think of the cake as an $N$-row by $M$-column matrix). The cake is quickly made, but a plain cake certainly doesn't look good! So, Sam plans to spread jam on the top surface of the cake. There are three types of jam: red, green, and blue, with the corresponding numbers $1, 2, 3$. To ensure the cake's visual appeal, Admin has issued a strict command: adjacent regions must not use the same type of jam. However, before receiving this command, Sam had already applied jam to the $K$-th row of the cake and cannot modify it. Now Sam wants to know: how many ways are there to apply the jam that will satisfy Admin? Please output the number of valid schemes modulo $10^6$. If no valid scheme exists, output $0$.

Input Format

The input consists of three lines. The first line: $N, M$; The second line: $K$; The third line: $M$ integers, representing the jam arrangement of the $K$-th row. Detailed meanings of the letters are as described in the problem statement. See the sample for further clarification.

Output Format

Output only one line, the total number of feasible schemes.

Sample 1

2 2
1
2 3

3

Data Range and Hints

For 30% of the data, $1≤N×M≤20$; For 60% of the data, $1≤N≤1000, 1≤M≤3$; For 100% of the data, $1≤N≤10000, 1≤M≤5$.