I: Palindrome Compliment

問題文

小池くんはチームメイトをよく褒めます。 彼はチームメイトである松崎くんを文字列 $S$ で褒めます。その形式は以下の条件を満たします。

• $Hoge, Zaki, O$ は小文字アルファベットのみからなる文字列
• $S = Hoge + Zaki + Hoge + O$ ($+$ は文字列の結合を表す)
• $S$ は回文

小池くんは$Hoge$の長さを$N$としたときに、松崎くんの褒め方が何通りあるのか気になりました。 3人目のチームメンバーにしてred coderであるあなたは小池くんの代わりに答えを計算することになりました。

文字列 $Zaki, O$ と 整数 $N$ が与えられるので、ありえる組み合わせの数を求めてください． なお、答えは非常に大きくなる可能性があるので、$10^9 + 7$ で割った 余りを出力してください。

制約

• $Zaki$ と $O$ は小文字アルファベットからなる文字列
• $1 \leq |Zaki| \leq 10^5$
• $1 \leq |O| \leq 10^5$
• $1 \leq N \leq 10^9$

入力

入力は以下の形式で標準入力から与えられます。

$Zaki$
$O$
$N$

出力

答えを1行に出力してください。

入出力例

入力例1

zaki
o
4

出力例1

0

入力例2

aab
aa
3

出力例2

26

入力例3

aaa
aaaa
3

出力例3

1