BRHWURD - Words
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
Added by: | Damon Doucet |
Date: | 2009-12-05 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 NODEJS OBJC PERL6 SQLITE VB.NET |