You are given two strings, \(A\) and \(B\), of lengths \(N\) and \(M\), respectively, containing lowercase English letters. You are also given a parameter \(K\). You take out \(K\) non-overlapping non-empty sub-strings from \(A\) and concatenate them in the order in which they appear in \(A\) to get a new string. Your task is to calculate the number of ways to make the new string and string \(B\) equal. Since the answer can be large, calculate it modulo \(10^9 + 7\).

Note that the two ways are different if at least one of the sub-strings is different at any position or the indices with which the sub-strings are made are different.

Input Format

• The first line contains a single integer \(N\), denoting the length of the string \(A\).
• The second line contains a single integer \(M\), denoting the length of the string \(B\).
• The third line contains a single integer \(K\), denoting the number of substrings you need to take from \(A\).
• The fourth line contains the string \(A\), containing lowercase English letters without spaces.
• The fifth line contains the string \(B\), containing lowercase English letters without spaces.

Output Format

Print the number of ways to build the string \(B\) using exactly \(K\) non-overlapping non-empty substrings from \(A\) modulo \(10^9 + 7\).

Constraints