B'Hamed has recently found a string t and suddenly became quite fond of it. He spent several days trying to find all occurrences of t in other strings he had. Finally he became tired and started thinking about the following problem. Given a string s how many ways are there to extract k xe2 x80 x89 xe2 x89 xa5 xe2 x80 x891 non-overlapping substrings from it such that each of them contains string t as a substring? More formally, you need to calculate the number of ways to choose two sequences a1, xe2 x80 x89a2, xe2 x80 x89..., xe2 x80 x89ak and b1, xe2 x80 x89b2, xe2 x80 x89..., xe2 x80 x89bk satisfying the following requirements: As the number of ways can be rather large print it modulo 109 xe2 x80 x89+ xe2 x80 x897. Input consists of two lines containing strings s and t (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89|s|, xe2 x80 x89|t| xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89105). Each string consists of lowercase Latin letters. Print the answer in a single line.'...