You live in a city with many roads extending far in the north-south direction and many roads extending far in the east-west direction. The distance between two adjacent north-south roads is $1\text{ km}$. Similarly, the distance between two adjacent east-west roads is $1\text{ km}$.

There is one city hall in this city. Let the intersection where the city hall is located be $(0,0)$. An intersection in this city is represented by two integers $i, j$ as $(i, j)$. That is, the intersection $(i, j)$ is the position reached by moving $i\text{ km}$ east (or $-i\text{ km}$ west if $i < 0$) and $j\text{ km}$ north (or $-j\text{ km}$ south if $j < 0$) from the intersection $(0,0)$.

The city hall keeps a dog named Joy. Joy has made a plan for walks over $K$ days. The walk plan is as follows:

• On the morning of the first day of the $K$ days, Joy is at the intersection $(0,0)$. Joy marks the intersection $(0,0)$. Joy does not mark any intersection other than $(0,0)$.
• Joy goes for a walk during the day for each of the $K$ days. A single day's walk consists of $N$ steps. In each step, Joy moves from the current intersection to an adjacent intersection and marks the destination. How Joy moves during the day is the same for every day.
• After the daytime movement is finished, Joy sleeps at the current intersection until the morning of the next day.

The city hall is discussing Joy's territory created by the walks over $K$ days. A region enclosed by four intersections $(a,b), (a+1,b), (a+1,b+1), (a,b+1)$ belongs to Joy's territory if Joy has marked all four of these intersections at least once.

You are to write a program that calculates the number of regions belonging to Joy's territory based on Joy's walk plan.

Since the roads in this city are very long and there are sufficiently many roads in both the north-south and east-west directions, Joy will never reach the end of a road or the edge of the city during the walks.

Input

Read the following input from standard input:

• The first line contains two integers $N$ and $K$ separated by a space. This indicates that each day's walk consists of $N$ steps and the walk plan spans $K$ days.
• The second line contains a string $S$ of length $N$. The $p$-th character $C_p$ ($1 \le p \le N$) from the left of string $S$ is one of 'E', 'N', 'W', 'S'. These characters represent the following:
  • If the character $C_p$ is 'E', it means moving to the intersection to the east in the $p$-th step.
  • If the character $C_p$ is 'N', it means moving to the intersection to the north in the $p$-th step.
  • If the character $C_p$ is 'W', it means moving to the intersection to the west in the $p$-th step.
  • If the character $C_p$ is 'S', it means moving to the intersection to the south in the $p$-th step.

Here, for an intersection $(i, j)$, the intersections to the east, north, west, and south are $(i+1, j)$, $(i, j+1)$, $(i-1, j)$, and $(i, j-1)$, respectively.

Output

Output the number of regions belonging to Joy's territory to standard output in a single line.

Constraints

All input data satisfy the following conditions:

• $1 \le N \le 100\,000$.
• $1 \le K \le 1\,000\,000\,000$.

Subtasks

Subtask 1 [5 points]

• $N \le 50$.
• $K = 1$.

Subtask 2 [10 points]

• $K = 1$.

Subtask 3 [23 points]

• $N \le 50$.

Subtask 4 [62 points]

• No additional constraints.

Examples

Input 1

12 1
EENWSEEESWWS

Output 1

3

Note

In this example, the walk is performed for 1 day. On the first day, Joy starts from the city hall and moves as shown in the figure below. Black circles are intersections marked by Joy, white circles are intersections not marked by Joy, the double circle is the intersection where the city hall is located, and the numbers represent each step.

Joy's movement path

In Example 1, the 3 regions indicated by the shaded area in the figure below belong to Joy's territory.

Joy's territory in Example 1

Input 2

12 2
EENWSEEESWWS

Output 2

7

Note

In Example 2, the walk is performed over 2 days. Each day's movement path is the same as in Example 1. When the walk is completed, the 7 regions indicated by the shaded area in the figure below belong to Joy's territory.

Joy's territory in Example 2

Input 3

7 1
ENNWNNE

Output 3

0

Note

In Example 3, there are no regions that belong to Joy's territory.

Input 4

16 5
WSESSSWWWEEENNNW

Output 4

21