405253: GYM101858 E End Game

The Vanguard guild has reached the last Aincrad floor: 100.

The guild wants to finish the game as soon as possible to free all the people trapped inside it, but you cannot rush, otherwise people may die fighting the last boss and you may lose the opportunity to finish it.

The Vanguard fought the final boss, Lavos, a number of times and now you know how it attacks and how should you fight it.

Lavos has a cyclic attack pattern $$$p$$$. Each attack is one of the following: Rain Destruction, Lavos Needle or Earthquake. As soon as you enter the boss room it starts it's attack in any position of it's pattern, uniformly distributed. After Lavos uses the attack at position $$$i$$$ of the pattern, the next attack will be $$$1$$$, if $$$i$$$ is the last attack of the pattern, or $$$i+1$$$, otherwise.

The only chance against this boss is one technique: the Omnislash. It consists of an attack sequence $$$t$$$, having three attack variations. Coincidently, each variation counters one of Lavos attacks.

Alpha variation counters Rain Destruction and causes $$$a$$$ damage to Lavos. Beta variation counters Lavos Needle and causes $$$b$$$ damage to Lavos. Charlie variation counters Earthquake and causes $$$c$$$ damage to Lavos.

You can't stop the Omnislash attack sequence and Omnislash attacks have the same duration as Lavos attacks (each Lavos attacks happen at the same time as Omnislash attacks).

You will use Omnislash as soon as Lavos starts attacking and you can only use Omnislash once. Either Lavos dies during Omnislash or you die after Omnislash finishes. You cannot be killed in the middle of Omnislash.

You already know that Lavos has a total of $$$h$$$ hit points.

The Vanguard needs to know what are the chances to defeat Lavos.

Lavos is considered defeated as soon as it's hit points get to zero or less. It loses $$$1$$$ hit point for every $$$1$$$ damage it receives.

The first line contains $$$4$$$ integers, $$$a$$$, $$$b$$$, $$$c$$$ and $$$h$$$ ($$$0 \le a, b, c \le 10^9$$$, $$$1 \le h \le 10^9$$$) — the damage Alpha, Beta and Charlie attack variations causes, and Lavos health.

The next line contains one string, $$$p$$$ ($$$1 \le |p| \le 2 \times 10^5$$$) — Lavos attack pattern. 'R' means Rain Destruction, 'N' means Lavos Needle and 'E' means Earthquake.

The next line contains one string, $$$t$$$ ($$$1 \le |t| \le |p|$$$) — Omnislash attack sequence. 'A' means Alpha variation, 'B' means Beta variation and 'C' means Charlie variation.

Print the probability to win against Lavos as two space-separated integers, $$$p$$$ and $$$q$$$, which $$$p/q$$$ is the answer and it's an irreducible fraction.

1 1 1 1
RNENR
ABC

3 5

3 1 2 3
RNENER
ABC

1 2