Setsuna with String

题号：NC219929
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

你有 $m$ 个长度为 $2$ 的仅包含小写英文字母的字符串。

问有多少个长度恰好为 $n$ 的仅包含小写英文字母的字符串，满足以上 $m$ 个字符串都不是该串的子串。

明确一下子串的定义，字符串 $s$ 是字符串 $t$ 的子串当且仅当能从 $t$ 的开头或结尾删去大于等于 $0$ 个字符得到 $s$ 。例如， $ab$ 是 $ab$ 的子串， $ab$ 是 $babb$ 的子串，但 $ab$ 不是 $acb$ 的子串。

为了防止答案过大，答案请对 $10^9+7$ 取模。

输入描述:

第一行两个正整数  。

接下来  行，每行一个长度为  的字符串，保证仅包含小写英文字母。

输出描述:

输出一个整数，表示满足条件的字符串个数，对  取模。

示例1

输入

复制

2 2
ab
bc

输出

复制

示例2

输入

复制

3 3
ab
aa
aa

输出

复制

题目描述

输入描述:

输出描述:

输入

输出

输入

输出

备注: