String Transformation — Suffix Removal Then Prepend

In each step, choose a non-empty proper suffix and move it to the front of the string; the string must become the target after exactly k steps. Different sequences of cut points are counted separately, even if the string is periodic. Output the answer modulo 10⁹+7.

输入格式

Three lines: src, target, and k. Each string has length 2..1000, 1≤k≤10⁶, and characters are a..z.

输出格式

Output the single integer required by the problem.

样例 1

输入：

ababab
ababab
1

输出：

2

样例 2

输入：

aaaa
aaaa
2

输出：

9

样例 3

输入：

ab
ba
2

输出：

0

样例说明

The answers to the three public examples are, in order: 2; 9; 0. All examples have been verified by independent small-scale enumeration or state search.