牛牛的斐波那契字符串

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

题目描述

定义字符串的斐波那契序列 $fibstr_1=A,fibstr_2=B$ ,当i>=3时 $fibstr_i=fibstr_{i-2}+fibstr_{i-1}$ 字符串的加法定义为字符串直接拼接。

给定A，B两个初始串，以及一个字符串S，牛牛想知道 $fibstr_n$ ,中包含了多少个S串。请统计数目告诉牛牛。由于这个数字很大，请输出答案mod $10^9+7$ 后的结果。

输入描述:

第一行输入一个正整数n表示第n个fibstr。

接下来三行分别输入三个字符串，A，B，S，表示两个初始串以及查询串。

所有输入的字符串仅由小写英文字母组成。

输出描述:

输出答案mod  后的结果

示例1

输入

复制

10
a b bab

输出

复制

说明

="bababbababbabbababbababbabbababbabbababbababbabbababbab"