Nine-Key Dictionary Input

Marko has discovered a new feature on his phone – nine-key input! His phone has a keyboard with digits laid out as follows:

	1	2 abc	3 def
	4 ghi	5 jkl	6 mno
	7 pqrs	8 tuv	9 wxyz

To input a word, Marko must press a key multiple times. More specifically, if a letter is the i-th letter on the key, Marko needs to press that key i times. For example, to input the word giht:

• Press key 4 once for g (first letter on key 4: ghi)
• Press key 4 three times for i (letter order: g, h, i)
• Press key 4 two times for h (g, h, i)
• Press key 8 once for t (first letter on key 8: tuv)

Marko has memorized his entire phone dictionary which consists of N words, each composed exclusively of lowercase letters. The total length of all words does not exceed \(10^9\) characters. Given a set of available keys, Marko wonders how many words in his dictionary can be typed using only the allowed keys.

The letter to key mapping is as follows (in \(\LaTeX\) format):

[ \begin{array}{ll} a,b,c & \to 2 \ d,e,f & \to 3 \ g,h,i & \to 4 \ j,k,l & \to 5 \ m,n,o & \to 6 \ p,q,r,s & \to 7 \ t,u,v & \to 8 \ w,x,y,z & \to 9 \end{array} ]

A word is considered typeable if for every letter in the word, the corresponding key is among the allowed keys provided in the input.

inputFormat

The input is given in the following format:

N
word_1
word_2
... 
word_N
allowed_keys

Where:

• N is an integer representing the number of words in the dictionary.
• Each word_i is a lowercase string representing a word in the dictionary.
• allowed_keys is a string consisting of digits (from 1 to 9) representing the keys available for input.

Note: The total length of all words does not exceed \(10^9\) characters.

outputFormat

Output a single integer representing the number of words in the dictionary that can be typed using only the allowed keys.

sample

4
giht
hello
world
dog
48

1

</p>