单词

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

题目描述

牛牛在学竞赛，但是由于学校领导的担心，要求牛牛在兼顾竞赛的情况下天天花 $40$ 分钟早读，牛牛看到一长串的英文单词差点晕了，但是突然想出了一个问题，但是他不会做，所以他想请教一下你。

有两个单词，他们非常的长，牛牛想将第一个单词提取出若干个区间，使得每一个区间都包含第二个单词，问这样提取组合的方案数。

题目中“提取出若干个区间”指的是选出若干个区间，并且这些区间互不相交。

比如说单词 $"aabbaba"$ ，其中一种提取组合就是 ${[1,3],[5,6]}$ ，提取出来的字符串就是 ${"aab","ab"}$ 。

容易发现一个单词的提取组合一共有 $2^n$ 种。

两行每行一个单词

一行一个整数表示方案数对取模的结果

示例1

复制

baba
ba

复制

示例2

复制

ababaaabababaaaabaaaababa
aba

复制

分别为两个单词的长度，单词只包含小写字母
对于的数据，
对于的数据，
对于的数据，
对于的数据，
对于的数据，