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 ≤ 105) — 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(109 + 7).

备注:

The sought way in the first sample is:ab → ab → ba → ba → abIn the second sample the two sought ways are:ababab → ababab → abababababab → ababab → ababab