题目描述

给你一个 $n\times m$ 的矩阵，再给你两个长度为 $n+m-1$ 的小写字母组成的字符串 A,B，问有多少种给矩阵在每个格子里填小写字母的方式，使得从矩阵的左上角到右下角（只能往右和往下），存在两条路径经过的字符分别组成 A 和 B。

求这样的矩阵的个数模 $1000000007$。

输入格式

第一行两个正整数 $n,m$。$(1\le n,m\le 8)$

第二行一个长度为 $n+m-1$ 的字符串 A。

第三行一个长度为 $n+m-1$ 的字符串 B。

输出格式

一行一个数表示答案。

样例

样例输入

2 2
aca
aba

样例输出

2