You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

染色

题目描述

有一个 $n$ 行 $m$ 列的格点图，你需要给每个点上染上 $2$ 种颜色中的一种，要求没有两个相邻点颜色相同。给定第一行与最后一行的染色，试求总染色方案数。

输入格式

第一行两个整数 $n,m$。

第二行 $m$ 个整数，第一行的染色方案，用 $0\sim 1$ 表示每种颜色。

第三行 $m$ 个整数，最后一行的染色方案，用 $0\sim 1$ 表示每种颜色。

输出格式

一个整数，表示答案。

输入输出样例 #1

输入 #1

2 2 
1 0
1 0

输出 #1

0

输入输出样例 #2

输入 #2

2 2 
0 1
1 0

输出 #2

1

数据范围

2 ≤ n ≤ 10³,1 ≤ m ≤ 10³