Word Cut

* 定义一轮操作：对于一个串，从任意地方截断，然后把两部分位置交换得到新的串。 * 对于$a$ 串一共进行$k$ 轮这种操作。 * 问从$a$ 串变到$b$ 串有多少种方法。 Translated by @frankchenfu

Let's consider one interesting word game. In this game you should transform one word into another through special operations. Let's say we have word $ w $ , let's split this word into two non-empty parts $ x $ and $ y $ so, that $ w=xy $ . A split operation is transforming word $ w=xy $ into word $ u=yx $ . For example, a split operation can transform word "wordcut" into word "cutword". You are given two words $ start $ and $ end $ . Count in how many ways we can transform word $ start $ into word $ end $ , if we apply exactly $ k $ split operations consecutively to word $ start $ . Two ways are considered different if the sequences of applied operations differ. Two operation sequences are different if exists such number $ i $ ( $ 1<=i<=k $ ), that in the $ i $ -th operation of the first sequence the word splits into parts $ x $ and $ y $ , in the $ i $ -th operation of the second sequence the word splits into parts $ a $ and $ b $ , and additionally $ x≠a $ holds.

The first line contains a non-empty word $ start $ , the second line contains a non-empty word $ end $ . The words consist of lowercase Latin letters. The number of letters in word $ start $ equals the number of letters in word $ end $ and is at least $ 2 $ and doesn't exceed $ 1000 $ letters. The third line contains integer $ k $ ( $ 0<=k<=10^{5} $ ) — the required number of operations.

Print a single number — the answer to the problem. As this number can be rather large, print it modulo $ 1000000007 $ $ (10^{9}+7) $ .

ab
ab
2

1

ababab
ababab
1

2

ab
ba
2

0

The sought way in the first sample is: ab $ → $ a|b $ → $ ba $ → $ b|a $ → $ ab In the second sample the two sought ways are: - ababab $ → $ abab|ab $ → $ ababab - ababab $ → $ ab|abab $ → $ ababab