## 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:

*empty string*"" denoting the language containing only the empty string, which has no characters at all.

ℒ("") = {""}*literal character*"*a*", where*a*∈ Σ, denoting the language containing only the character*a*.

ℒ("*a*") = {"*a*"}*wildcard*"" denoting the language containing every single character in Σ.`.`

ℒ("`.`

") = {"*a*" :*a*∈ Σ}

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

*alternation*"*R*`|`

*S*" denoting the set union of languages described by*R*and*S*.

ℒ("*R*`|`

*S*") = ℒ(*R*) ∪ ℒ(*S*)

For example, if*R*describes {"ab", "c"} and S describes {"ab", "d", "ef"}, expression "*R*`|`

*S*" describes {"ab", "c", "d", "ef"}.*concatenation**RS*denoting the language ℒ("*R**S*") = { "αβ" : α ∈ ℒ(*R*) and β ∈ ℒ(*S*)}.

For example regular expression "`(ab|c)(d|ef)`

" represents {"abd", "abef", "cd", "cef"}.*Kleene star*"*R*`*`

" denoting the smallest superset of language described by*R*that contains empty string and is closed under string concatenation. This is the language of all strings that can be made by concatenating any finite number (including zero) of strings from language described by*R*.

For example, "`(0|1)*`

" is the language of all finite binary strings (including the empty string), and "`(ab|c)*`

" represents {"", "ab", "c", "abab", "abc", "cab", "cc", "ababab", "abcab", ... }.*parentheses*"`(`

*R*`)`

" denoting the language described by*R*.

ℒ("`(`

*R*`)`

") = ℒ(*R*)

For example, "`(ab)*`

" describes {"", "ab","abab","ababab",...}.

To avoid parentheses it is assumed that the Kleene star has the highest priority, then concatenation and then alternation. If there is no ambiguity then parentheses may be omitted. For example, "`(ab)c`

" can be written as "`abc`

", and "`a|(b(c*))`

" can be written as "`a|bc*`

".

**Examples:**

- ℒ("
`(a|b)*`

") denotes the language of all strings with no symbols other than "a" and "b", including the empty string: {"", "a", "b", "aa", "ab", "ba", "bb", "aaa", ...} - ℒ("
`a|b*`

")={"", "a", "b", "bb", "bbb", ...} -
If Σ={"0","4","a"} then ℒ("
`4.|0`

")={"40", "44", "4a", "0"}. `ℒ("ab*(c|)`

") denotes the language of strings starting with "a", then zero or more "b"s and finally optionally a "c": {"a", "ac", "ab", "abc", "abb", "abbc", ...}

### The Task

Consider that you have-
a finite alphabet Σ, where 1 ≤ |Σ| ≤ 100 and Σ does not contain characters:
"
`(`

","`)`

","`.`

","`|`

", "`*`

"; -
a regular expression
*A*, where 0 ≤ |*A*| ≤ 100, where |*A*| means the number of characters in the regular expression string*A*; -
a regular expression
*B*, where 0 ≤ |*B*| ≤ 100, where |*B*| means the number of characters in the regular expression string*B*; -
a number
*n*, where 0 ≤*n*≤ 100.

*S*|, where

*S*= {

*s*:

*s*∈ ℒ(

*A*), (∃

*x*∈ ℒ(

*B*) :

*x*is substring of

*s*), |

*s*| =

*n*}. It is assured by the task, that 0 ≤ |

*S*| ≤ 2

^{31}.

### 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