让我们考虑一个有趣的文字游戏。在这个游戏中你要通过特殊的操作将一个单词变成另一个单词。
假设我们有单词 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