import java.math.BigInteger;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {

    public int[] matrix = null;
    public int color = 0;
    public int n = 0;
    
    public int total = 0;
    public List<List<Integer>> list = new ArrayList<List<Integer>>();
    
    /**
     * 分出隔离的区域
     */
    public void split() {
        int a = 0;
        while (a < matrix.length) {
            if (matrix[a] == 0) {
                List<Integer> set = new ArrayList<>();
                list.add(set);
                matrix[a] = -1;
                set.add(a);
                search(a, set);
            }
            a++;
        }
    }
    
    private void search(int a, List<Integer> set) {
        if (a >= n) {
            if (matrix[a-n] == 0) {
                matrix[a-n] = -1;
                set.add(a-n);
                search(a-n, set);
            }
            if (a+1<2*n && matrix[a+1] == 0) {
                matrix[a+1] = -1;
                set.add(a+1);
                search(a+1, set);
            }
            if (a-1>n-1 && matrix[a-1] == 0) {
                matrix[a-1] = -1;
                set.add(a-1);
                search(a-1, set);
            }
        } else {
            if (matrix[a+n] == 0) {
                matrix[a+n] = -1;
                set.add(a+n);
                search(a+n, set);
            }
            if (a+1<n && matrix[a+1] == 0) {
                matrix[a+1] = -1;
                set.add(a+1);
                search(a+1, set);
            }
            if (a-1>-1 && matrix[a-1] == 0) {
                matrix[a-1] = -1;
                set.add(a-1);
                search(a-1, set);
            }
        }
    }
    
    /**
     * 搜索
     */
    public BigInteger print(List<Integer> set, BigInteger count) {
        BigInteger total = BigInteger.ZERO;
        List<Integer> recycle = new ArrayList<Integer>();
        recycle.addAll(set);
        int o = set.remove(0);
        for (int c=1;c<=color;c++) {
            if (o < n) {
                if ((o+1<n && c == matrix[o+1])
                        || (o > 0 && c == matrix[o-1])
                        || (c == matrix[o+n])) {
                    continue;
                } else {
                    matrix[o] = c;
                }
            } else {
                if ((o+1<2*n && c == matrix[o+1])
                        || (o > n && c == matrix[o-1])
                        || c == matrix[o-n]) {
                    continue;
                } else {
                    matrix[o] = c;
                }
            }
            if (set.size() == 0) {
                total = total.add(BigInteger.ONE);
            } else {
                total = print(set, total);
            }
            // 还原
            matrix[o] = -1;
        }
        // 还原
        set.add(0, o);
        return count.add(total);
    }
    
    public static void main(String[] args) {
        Main print = new Main();
        Scanner scanner = new Scanner(System.in);
        print.n = scanner.nextInt();
        print.color = scanner.nextInt();
        print.matrix = new int[2*print.n];
        for (int i=0;i<2*print.n;i++) {
            print.matrix[i] = scanner.nextInt();
        }
        scanner.close();
        
        print.split();
        BigInteger b = BigInteger.ONE;
        // 总方案数=各子区域方案数的积（高精度乘）
        for (int i=0;i<print.list.size();i++) {
            BigInteger count = print.print(print.list.get(i), BigInteger.ZERO);
            b = b.multiply(new BigInteger(String.valueOf(count)));
            b = b.mod(new BigInteger("1000000009"));
        }
        System.out.println(b.intValue());
    }
}