← 返回题目列表

Codeforces · 176/B

B. 字切

中文机器翻译题面 查看原题

让我们考虑一个有趣的文字游戏。在这个游戏中你要通过特殊的操作将一个单词变成另一个单词。

假设我们有单词 w,我们将这个单词分成两个非空部分 x 和 y,这样 w = xy。分割操作是将单词 w = xy 转换为单词 u = yx。例如,分割操作可以将单词“wordcut”转换为单词“cutword”。

给你两个单词开始和结束。如果我们连续对单词开始应用 k 个分割操作,请计算有多少种方法可以将单词开始转换为单词结束。

如果应用操作的顺序不同,则两种方式被认为是不同的。如果存在这样的数字 i (1 ≤ i ≤ k),则两个操作序列是不同的,即在第一个序列的第 i 次操作中,单词分为 x 和 y 部分,在第二个序列的第 i 次操作中,单词分为 a 和 b 部分,并且另外 x ≠ a 成立。

输入

第一行包含非空字开始,第二行包含非空字结束。这些单词由小写拉丁字母组成。单词开头的字母数等于单词结尾的字母数,并且至少为 2 个且不超过 1000 个字母。

第三行包含整数 k (0 ≤ k ≤ 105) — 所需的操作次数。

输出

打印一个数字——问题的答案。由于该数字可能相当大,因此将其打印为对 1000000007 (109 + 7) 取模。

示例

输入 #1

ab
ab
2

输出 #1

1

输入 #2

ababab
ababab
1

输出 #2

2

输入 #3

ab
ba
2

输出 #3

0

注意

第一个示例中寻求的方法是:

ab → a|b → ba → b|a → ab

在第二个示例中,寻求的两种方法是:

- ababab  →  abab|ab  →  ababab
- ababab  →  ab|abab  →  ababab