C. Enigmatic Lights
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output
I go back to December all the time
—Back to December

This is a harder version of "Problem E - Erratic Lights" from NWERC 2025 (https://2025.nwerc.eu/problem-set.pdf).

Last December, you spent many days preparing a stall for the Christmas market. When you finally plugged in the string of lights, you discovered you had brought the wrong one: instead of all-blue lights, the bulbs were a mix of red, green, and blue. While leaning against the stall in despair, you accidentally bumped into one of the bulbs and watched it immediately change colour. After a bit of experimenting, you concluded that every time you touched a bulb, it would randomly become red, green, or blue — and you assumed each colour was equally likely.

Now it is February, and you are looking back on what happened. The "equally likely" assumption turns out to have been wrong: those bulbs did not choose the three colours uniformly. In fact, each time you touch a bulb, it becomes red with probability $$$p_r$$$, green with probability $$$p_g$$$, and blue with probability $$$p_b$$$, where $$$p_r + p_b + p_g = 1$$$! These probabilities are fixed for the entire string and do not depend on which bulb you touch or what colour it currently has.

You reasoned that it would take more than $$$5$$$ hours to order a new string of blue lights, so at the very least you wanted to turn all the lights to the same colour, no matter which colour it is. But with these new probabilities, your original strategy was suboptimal! Thus you must solve the problem again — what is the minimum expected number of touches to have all the bulbs be the same colour?

Input

The input consists of

  • One line consisting of $$$4$$$ integers $$$n, p_r, p_g, p_b$$$ $$$(1\leqslant n \leqslant 500, 1\leqslant p_r,p_g,p_b \leqslant 98, p_r + p_g + p_b = 100)$$$, the number of lights, and the percentage probability of a light turning red, green, or blue.
  • One line with $$$n$$$ characters, each of which is "r", "g", or "b", indicating the original configuration of the lights.
Output

Output the expected number of times you need to touch a light bulb to make all of them have the same colour, assuming an optimal strategy that tries to minimize the expected number of touches.

Your answer should have an absolute or relative error of at most $$$10^{-6}$$$.

Examples
Input
3 25 25 50
bgr
Output
4.0
Input
4 50 30 20
rrrr
Output
0.0
Note

In the first test case, one optimal strategy is to touch any non-blue lightbulb until they are all blue. This strategy requires $$$4$$$ lightbulb touches in expectation.

In the second test case, all the bulbs are the same colour already, so nothing needs to be done.