Butch has a favorite word W (1 ≤ length ≤ 10), and a bucket of letters. He has L (1 ≤ L ≤ 26) different letters, and Ci (1 ≤ Ci ≤ 5) of each.

He wants you to count how many ways he can make this word with the buckets.

If Butch tells you that he has a certain amount of a letter, he won't list the letter again.

The number of ways would be how many of letter 1 times how many of letter 2 times how many of letter 3...

Remember that if a letter isn't listed, then he has 0 of those letters in his bucket.

Input

Line 1: A single integer, L
Line 2: A line of text (not necessarily a real word), between 1 and 10 letters long, all lowercase.
Lines 3..L+2: A lowercase letter, and Ci, space separated.

Output

Line 1: A single integer, the number of ways he can make the word.

Example

Input:
6
dog
a 4
d 3
g 5
l 2
o 3
m 4

Output:
45