At RHHS, the school is on fire every other day, because safety is our number one priority. After administration has decided enough was enough, they decided to place detailed evacuation plans in each and every classroom to ensure everyone's safety during fire evacuations.
An evacuation plan consists of a list of movements in cardinal directions (North, South, East, West), which detail the exact movements a student must make in order to make it to safety.
One such evacuation plan may be
NNWS, which describes an evacuation plan where the student must move one meter north, one meter north, one meter west, then one meter south in order to reach safety.
However, administration has decided that these evacuation plans were too easy to follow, and did not foster the academic atmosphere RHHS is so famously known for having. As a result, administration decided to encode the evacuation plans with a different encoding for each room.
With this encoding, each cardinal direction is replaced with a string of letters, and the final evacuation plan is the concatenation of this string of letters. For example, the following mapping represents a possible encoding:
N → AA S → A E → B W → AB
With this encoding, our original evacuation plan of
A side effect of this encoding is that it may represent multiple possible original evacuation plans. With the above encoding,
AAAAABA could not only represent
NNWS, but also
Given an encoding and an evacuation plan, determine the number of possible distinct destinations the evacuation plan could lead to.
The first four lines will contain the encoding for North, South, East, and West respectively. Each encoding will not exceed characters. The next line will contain an evacuation plan encoded with the given encoding, of length .
For test cases worth 20 of 100 points, .
Output a single integer representing the number of possible distinct destinations the evacuation plan may lead to.
AA A B AB AAAAABA
Explanation of Sample Output
The possible original evacuation plans the encoded plan may represent are as follows:
NNSES NNWS NSNES NSSSES NSSWS SNNES SNSSES SNSWS SSNSES SSNWS SSSNES SSSSSES SSSSWS
However, many of them represent the same destination (for example,
NSNES are both syntactically identical to
6 of these plans lead to a distinct location.