B. Разрезание слов
ограничение по времени на тест
2 seconds
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Рассмотрим одну интересную игру со словами. В этой игре требуется из одного слова получить другое посредством специальных операций.

Пусть у нас есть слово w, разделим это слово на две непустые части x и y так, что w = xy. Операцией split, назовем преобразование слова w = xy в слово u = yx. Например, слово «wordcut» посредством одной операции split можно преобразовать в слово «cutword».

Вам даны два слова start и end. Посчитайте сколькими способами можно получить из слова start слово end, применив к слову start последовательно ровно k операций split.

Два способа считаются различными, если различаются последовательности примененных операций. Две последовательности операций различны, если существует такой номер i (1 ≤ i ≤ k), что в i-ой операции первой последовательности слово делится на части x и y, в i-ой операции второй последовательности слово делится на части a и b, и при этом x ≠ a.

Входные данные

В первой строке записано непустое слово start, во второй — непустое слово end. Слова состоят из строчных латинских букв. Количество букв в слове start совпадает с количеством букв в слове end и не превышает 1000 букв. Гарантируется, что слова start и end состоят из не менее 2 букв.

В третьей строке записано целое число k (0 ≤ k ≤ 105) — требуемое количество операций.

Выходные данные

Выведите единственное число — ответ на задачу. Так как это число может оказаться достаточно большим, выведите остаток от деления его на 1000000007 (109 + 7).

Примеры
Входные данные
ab
ab
2
Выходные данные
1
Входные данные
ababab
ababab
1
Выходные данные
2
Входные данные
ab
ba
2
Выходные данные
0
Примечание

В первом примере искомый способ:

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

Во втором примере искомые два способа:

  • ababab  →  abab|ab  →  ababab
  • ababab  →  ab|abab  →  ababab