这天，Sleeping Elephant 决定在评测记录上作画——画出一个绿色的 TLE 图案。
Sleeping Elephant 提交的题目共有 个测试点，可以看作有 个位置的网格图，从上到下分别为第 到第 行，从左到右分别为第 列到第 列。由于 Sleeping Elephant 写的不是正解，其中每个位置显示的评测状态可能是 AC（绿色）或 WA（红色）。
T 图案的形状如图：
L 图案的形状如图：
E 图案的形状如图：
其中：
- S 代表单个绿色格子。
- A 代表从该位置开始向上延展的若干（）个绿色格子。
- B 代表从该位置开始向下延展的若干（）个绿色格子。
- C 代表从该位置开始向左延展的若干（）个绿色格子。
- D 代表从该位置开始向右延展的若干（）个绿色格子。
例如，下图包含 个合法的 T 图案， 个合法的 L 图案和 个合法的 E 图案：
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
S |
|
|
|
|
|
|
| S |
S |
S |
S |
|
S |
|
|
S |
S |
S |
|
|
S |
|
|
|
S |
|
|
S |
|
|
|
|
S |
|
|
|
S |
S |
|
S |
|
|
|
|
S |
|
|
|
|
|
|
S |
|
|
|
|
S |
|
|
|
|
|
|
S |
S |
|
|
|
S |
|
|
|
|
|
|
S |
|
|
|
|
|
|
|
|
|
|
|
S |
S |
S |
S |
而下图只包含 个合法的 L 图案，不包含合法的 T 图案和合法的 E 图案：
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
S |
|
|
|
|
|
|
|
S |
S |
S |
|
S |
|
|
S |
S |
S |
|
|
S |
|
|
|
S |
|
|
S |
|
|
|
|
S |
|
|
|
S |
|
|
S |
|
|
|
|
S |
|
|
|
|
|
|
S |
|
|
|
|
S |
|
|
|
|
|
|
S |
|
|
|
|
S |
|
|
|
|
|
|
S |
S |
|
|
|
|
|
|
|
|
|
|
S |
S |
S |
S |
将上面两张图片上下拼接起来，我们就得到了样例。
已知 Sleeping Elephant 可以把任意多个绿色格子变为红色（可以是 个，但不能把红色格子变成绿色），请求出他可以画出的不同的合法的 T 图案、合法的 L 图案和合法的 E 图案的数量。
答案对 取模。
