ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

USU Junior Contest, October 2007

About     Problems     Submit solution     Judge status     Standings
Contest is over

B. Alchemy

Time limit: 1.0 second
Memory limit: 64 MB
Lich Sandro recently became an expert in alchemy and is very glad because of it. Sure enough, because this skill allows to mix simple potions to obtain more complex ones. Any character (even not skilled in alchemy) is able to make 3 simple potions: red, blue, and yellow. A single reagent is sufficient to make any of them, but the same reagent cannot be used to make potions of different colors. All reagents can be divided into 3 groups according to this rule: yellow (sulphur, unicorn's horn, a poppy boll…), blue (a piece of a meteor, a fang of a dragon turtle…) and red (dragon's eye, ruby, gog's blood…).
Every character would like to prepare other potions. In order to achieve that it is necessary to learn alchemy and to upgrade this skill. A novice alchemist is able to mix the basic potions: yellow and red, red and blue, or blue and yellow to obtain an orange, violet or green potion, respectively. These potions are called composite. An expert alchemist is also able to mix basic and composite potions without messing up their layers (this may lead to an explosion!).
Sandro has 3 bags of reagents, and each bag contains reagents of only one color. There are B blue, R red, and Y yellow reagents. Sandro's collection of reagents is extraordinary, since all the reagents are different! K reagents of different colors are required to make a potion that makes it posssible to breathe under water. The recipe of this potion is known, and now Sandro would like to know the number of possible ways to prepare it.

Input

The first line contains integers B, R, and Y; 1 ≤ B, R, Y ≤ 100. Then the recipe of the potion is given: the second line contains a positive integer K; the next K lines contain the colors of the required reagents (“Blue”, “Red”, or “Yellow”). Each word occurs at most once.

Output

Output the number of possible ways to choose a set of reagents to make the potion (sets differing in one or more reagent are considered different; the order of reagents in a set doesn't matter).

Sample

inputoutput
2 3 5
3
Red
Yellow
Blue
30
Problem Author: Alexander Ipatov
Problem Source: USU Junior Contest, October 2007
To submit the solution for this problem go to the Problem set: 1573. Alchemy