Fire Evacuation Plan


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 NNWS becomes AAAAABA.

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 SSSSSES.

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 128 characters. The next line will contain an evacuation plan encoded with the given encoding, of length L (1 ≤ L ≤ 2500)


Output a single integer representing the number of possible distinct destinations the evacuation plan may lead to.

Example input
Example output
Time and memory limit:

  • 2 seconds
  • 256MB

Problem source: DMOJ