#365. 斐波那契字符串

给定两个字符串 $S_0,S_1$。

对于 $n>1$，定义 $S_n=S_{n-2}+S_{n-1}$，其中 + 表示拼接操作。

求出 $S_n$ 中包含的 $T$ 串个数。

第一行三个字符串 $S_0,S_1,T$，用空格隔开。

然后一行一个整数 $n$ 。

输出一行一个整数表示答案。

样例输入1

AC AC AC
3

样例输出1

3

样例输入2

ACA CB AC
2

样例输出2

2

用 $|S|$ 表示字符串 $S$ 的长度。

$1\leq |S_0|,|S_1|\leq 100,|T|=2,0\leq n\leq 60$，字符串只包含大写字母。