Problem Statement

You are given two strings s and t of equal length n . You are allowed to perform the following operation on the string s exactly k times: In one operation, remove a non-empty suffix of s (of length l , where 1 ≤ l < n ) and prepend it to the beginning of s . For example, if s = "abcd" and you choose to remove the suffix "cd" (of length 2), the result after the operation would be "cdab" . Your task is to determine how many distinct ways you can transform the string s into the string t in exactly k operations using the operation described above. Two ways are considered different if the sequence of chosen suffix lengths differs at some operation, even when the intermediate strings look the same. Since the number of ways can be large, return the result modulo 10 9 + 7 . Input Format The first line contains the string s of length n . The second line contains the string t of length n . The third line contains the integer k . Output Format A single integer: the number of distinct ways t