Programming assignment A4M33PAL

The Word Counter

Definition of Regular Expressions

Regular expressions consist of constants and operator symbols that denote sets of strings (we call it language and denote it by ℒ) and operations over these sets, respectively. The following definition is based on standard (You can found it in most textbooks on formal language theory. [HMU] [JP] ).
Given a finite alphabet Σ, the following constants are defined as regular expressions:

Given regular expressions R and S, the following operations over them are defined to produce regular expressions:

Examples:

The Task

Consider that you have Your task is to compute a number of strings |S|, where S = { s : s ∈ ℒ(A), (∃x ∈ ℒ(B) : x is substring of s), |s| = n }. It is assured by the task, that 0 ≤ |S| ≤ 231.

Input

Input consists of the description of the task which has four lines. The first line contains the finite alphabet Σ as a string of characters, where every character of the string belongs to Σ. The second line contains the regular expression A. The third line contains the regular expression B. Finally, the last line contains the number n.

Output

The output contains a single line with the number |S|.

Examples:

Input:

cab
.*
aa|bb
3

The following properties hold according to the input:
Σ={"a","b","c"}
ℒ(A)={"","a","b","c","aa","ab","ac","ba",...}
ℒ(B)={"aa","bb"}
S={"aaa","baa","caa","aab","aac","abb","bbb","cbb","bba","bbc"}

Output:

10

Input:

10
1.*0
()
12

The following properties hold according to the input:
Σ={"0","1"}
ℒ(A)={"10","100","110","1000","1010","1100","1110",...}
ℒ(B)={""}
S={"100000000000","100000000010","100000000100","100000000110",...}

Output:

1024

Input:

0123456789
.*
1|22|333|4444|55555|666666|7777777|88888888|999999999
9

The following properties hold according to the input:
Σ={"0","1","2","3","4","5","6","7","8","9"}
ℒ(A)={"0","1","2",...}
ℒ(B)={"1","22","333",...}
S={"100000000","123555554",...}

Output:

649931007

More public data ...