题目背景

Manao 正在制作一款二维像素风游戏。为了让游戏场景更有层次感，他准备在宽度为 $W$ 的屏幕上依次绘制 $N$ 座山峰。

每座山峰都是一个等腰直角三角形。后绘制的山峰会覆盖先绘制的山峰，因此，最终画面中一座山峰可能只露出一部分，甚至完全不可见。

Manao 不小心遗失了所有山峰峰顶的横坐标，只保留了每座山峰的高度，以及最终画面中每座山峰在哪些列仍然可见。请你根据这些信息，统计可能的绘制方案数。

题目描述

屏幕共有 $W$ 列，列编号从 $0$ 到 $W-1$。屏幕高度可以认为是所有山峰高度的最大值。

共有 $N$ 座山峰，编号为 $0,1,\ldots,N-1$，并按照编号从小到大的顺序依次绘制。

第 $i$ 座山峰的高度为 $h_i$，其峰顶横坐标记为 $X_i$，满足：

$$0\le X_i<W.$$

峰顶纵坐标为 $h_i-1$。在第 $x$ 列中，第 $i$ 座山峰覆盖的像素数量为：

$$\max\bigl(0,\ h_i-|x-X_i|\bigr).$$

也就是说，如果该值为 $k>0$，那么这座山峰会覆盖第 $x$ 列中从底部开始的 $k$ 个像素。

绘制山峰时，后绘制的山峰会覆盖同一像素位置上先绘制的山峰。

对于每座山峰 $i$，给定一个长度为 $W$ 的字符串 $s_i$：

• 若 $s_i[x]=\texttt{X}$，表示最终画面中第 $x$ 列至少有一个像素属于第 $i$ 座山峰；
• 若 $s_i[x]=\texttt{-}$，表示最终画面中第 $x$ 列没有任何像素属于第 $i$ 座山峰。

请统计满足所有高度与可见性信息的峰顶横坐标序列：

$$(X_0,X_1,\ldots,X_{N-1})$$

的数量。

由于答案可能很大，请输出答案对 $1\,000\,000\,009$ 取模后的结果。

保证至少存在一种合法方案。

输入格式

第一行包含两个整数 $N,W$，分别表示山峰数量和屏幕宽度。

第二行包含 $N$ 个整数：

$$h_0,h_1,\ldots,h_{N-1},$$

其中 $h_i$ 表示第 $i$ 座山峰的高度。

接下来 $N$ 行，第 $i$ 行包含一个长度为 $W$ 的字符串 $s_i$，描述第 $i$ 座山峰在最终画面中的可见列。

输出格式

输出一个整数，表示合法峰顶横坐标序列的数量对 $1\,000\,000\,009$ 取模后的结果。

数据范围

对于所有测试数据：

• $1\le N\le 10$；
• $1\le W\le 50$；
• $1\le h_i\le 50$；
• $s_i$ 的长度均为 $W$；
• $s_i$ 只包含字符 X 和 -；
• 至少存在一种合法方案。

样例 1

输入

3 6
2 3 2
------
XXXX--
---XXX

输出

4

说明

第 $1$ 座和第 $2$ 座山峰的峰顶位置可以唯一确定。

第 $0$ 座山峰的峰顶可以位于第 $1,2,3,4$ 列，因此共有 $4$ 种方案。

样例 2

输入

3 13
4 3 4
XXXXX--------
----------XXX
----XXXXXXX--

输出

4

说明

三座山峰的峰顶横坐标依次可能为：

(2, 10, 7)
(2, 11, 7)
(3, 10, 7)
(3, 11, 7)

因此答案为 $4$。

样例 3

输入

4 9
13 2 3 2
XXXXXXXXX
-XXX-----
----XXXXX
-----XXX-

输出

9

样例 4

输入

5 7
8 2 9 3 10
X------
-------
------X
-------
XXXXXXX

输出

98