Substring Concatenation Count

You are given two strings A and B consisting only of lowercase English letters, and an integer k. The task is to select exactly k non‐overlapping non-empty substrings from A and then concatenate them in the order in which they appear in A to form a new string. Count the number of ways to choose these substrings so that the resulting string is exactly equal to B. Note that even if the chosen substrings are identical, if their positions in A differ, they are considered different.

Formally, let A be of length n and B of length m. We are to pick indices such that the substrings A[i₁...j₁], A[i₂...j₂], ..., A[i_k...j_k] (with 1 ≤ i₁ ≤ j₁ < i₂ ≤ j₂ < ... < i_k ≤ j_k ≤ n) satisfy \[ A[i_1:j_1] \; + \; A[i_2:j_2] \; + \; \cdots \; + \; A[i_k:j_k] \; = \; B, \] where the '+' denotes string concatenation. Compute the total number of valid ways to achieve this.

Note: There is no modulus specified; output the exact count.

inputFormat

The input consists of three lines:

1. The first line contains the string A.
2. The second line contains the string B.
3. The third line contains the integer k.

outputFormat

Output a single integer representing the number of ways to choose exactly k non-overlapping non-empty substrings from A that, when concatenated in order, equal B.

sample

abc
abc
1

1