E. Three Kingdoms
time limit per test
0.25 seconds
memory limit per test
32 megabytes
input
standard input
output
standard output

Joey and Grey are playing a poker game.

Initially, Joey has $$$n$$$ poker cards and Grey has none. They would repeat the following steps to help Grey get as many cards as possible:

$$$1$$$. Randomly pick a card from the card pile. This card is called FATE. Since the pile is very large and contains much more cards than one pack, the probability for one to pick/get cards of hearts, spades, diamonds and clubs will always be $$$a$$$, $$$b$$$, $$$c$$$, $$$d$$$ respectively.

$$$2$$$. Joey can (not must) use one card he owned to exchange the FATE, that means the FATE will be changed by the one Joey uses (Joey will lose this one) and Joey will get the old FATE card in step $$$1$$$. If Joey uses one card of spade in this process, he will get another new card randomly from the pile.

$$$3$$$. If now the FATE is spade or club, Grey can get this card and start another round from step $$$1$$$, otherwise they stop repeating and begin to count how many cards Grey got.

They are curious about one question — if they operate optimally, how many cards could Grey get expected.

Input

The first line of input contains four integers, they are $$$100a$$$, $$$100b$$$, $$$100c$$$, $$$100d$$$. We guarantee that $$$0\leq 100a,100b,100c,100d \leq 100$$$ and $$$100a+100b+100c+100d=100$$$.

The second line of input is a string of length $$$n$$$ to represent the cards Joey owns originally, in which $$$H$$$ represents hearts, $$$S$$$ for spades, $$$D$$$ for diamonds and $$$C$$$ for clubs. We promise $$$1\leq n \leq 100$$$.

Output

Just one integer represented the maximum expected number of cards modulo $$$998244353$$$ Grey can get. If this number is infinity, please output $$$INF$$$.

Examples
Input
25 25 25 25
S
Output
6
Input
0 100 0 0
HSDC
Output
INF
Note

For the first example, the maximum expected number of cards Grey can get is $$$6$$$. I can not provide all the cases here (which are infinity), but one possible case that Grey gets $$$6$$$ cards is that:

The first round, they picked one heart. Joey used his spade to exchange it and got a new club from the pile. Now Joey has two cards, one heart and one club. Grey got the spade card and started a new round.

The second round to the fifth round, they kept picking club from the pile and Joey did nothing. Grey got $$$4$$$ clubs.

The sixth round, they picked one diamond. Joey used his club to exchange it. Now Joey owns two cards, one heart and one diamond.

The seventh round, they picked one heart, it can be proved that they will stop here.

For the second example, obviously, Grey can get infinity number of cards, so the output is $$$INF$$$.