Du bor i en stad med många vägar som sträcker sig långt i nord-sydlig riktning och många vägar som sträcker sig långt i öst-västlig riktning. Avståndet mellan två intilliggande nord-sydliga vägar är $1\text{ km}$. På samma sätt är avståndet mellan två intilliggande öst-västliga vägar $1\text{ km}$.

Det finns ett stadshus i denna stad. Låt korsningen där stadshuset ligger vara $(0,0)$. En korsning i denna stad representeras av två heltal $i, j$ som $(i, j)$. Det vill säga, korsningen $(i, j)$ är den position som nås genom att flytta $i\text{ km}$ österut (eller $-i\text{ km}$ västerut om $i < 0$) och $j\text{ km}$ norrut (eller $-j\text{ km}$ söderut om $j < 0$) från korsningen $(0,0)$.

Stadshuset har en hund som heter Joy. Joy har gjort en plan för promenader under $K$ dagar. Promenadplanen ser ut som följer:

• På morgonen den första dagen av de $K$ dagarna befinner sig Joy vid korsningen $(0,0)$. Joy markerar korsningen $(0,0)$. Joy har inte markerat någon annan korsning än $(0,0)$.
• Joy går på en promenad under dagen för var och en av de $K$ dagarna. En enskild dags promenad består av $N$ steg. I varje steg rör sig Joy från den nuvarande korsningen till en intilliggande korsning och markerar destinationen. Hur Joy rör sig under dagen är detsamma varje dag.
• Efter att förflyttningen under dagen är avslutad sover Joy vid den nuvarande korsningen fram till morgonen nästa dag.

Stadshuset diskuterar Joys revir som skapats av promenaderna under $K$ dagar. Ett område som omges av fyra korsningar $(a,b), (a+1,b), (a+1,b+1), (a,b+1)$ tillhör Joys revir om Joy har markerat alla fyra av dessa korsningar minst en gång.

Du ska skriva ett program som beräknar antalet områden som tillhör Joys revir baserat på Joys promenadplan.

Eftersom vägarna i denna stad är mycket långa och det finns tillräckligt många vägar i både nord-sydlig och öst-västlig riktning kommer Joy aldrig att nå slutet av en väg eller kanten av staden under promenaderna.

Indata

Läs följande indata från standard inmatning:

• Den första raden innehåller två heltal $N$ och $K$ separerade med ett mellanslag. Detta anger att varje dags promenad består av $N$ steg och att promenadplanen sträcker sig över $K$ dagar.
• Den andra raden innehåller en sträng $S$ av längd $N$. Det $p$-te tecknet $C_p$ ($1 \le p \le N$) från vänster i strängen $S$ är ett av 'E', 'N', 'W', 'S'. Dessa tecken representerar följande:
  • Om tecknet $C_p$ är 'E' betyder det att flytta till korsningen österut i det $p$-te steget.
  • Om tecknet $C_p$ är 'N' betyder det att flytta till korsningen norrut i det $p$-te steget.
  • Om tecknet $C_p$ är 'W' betyder det att flytta till korsningen västerut i det $p$-te steget.
  • Om tecknet $C_p$ är 'S' betyder det att flytta till korsningen söderut i det $p$-te steget.

Här, för en korsning $(i, j)$, är korsningarna österut, norrut, västerut och söderut $(i+1, j)$, $(i, j+1)$, $(i-1, j)$ respektive $(i, j-1)$.

Utdata

Skriv ut antalet områden som tillhör Joys revir till standard utmatning på en enda rad.

Begränsningar

Alla indata uppfyller följande villkor:

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

Deluppgifter

Deluppgift 1 [5 poäng]

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

Deluppgift 2 [10 poäng]

• $K = 1$.

Deluppgift 3 [23 poäng]

• $N \le 50$.

Deluppgift 4 [62 poäng]

• Inga ytterligare begränsningar.

Exempel

Indata 1

12 1
EENWSEEESWWS

Utdata 1

3

Förklaring

I detta exempel genomförs promenaden under 1 dag. Den första dagen startar Joy från stadshuset och rör sig som visas i figuren nedan. Svarta cirklar är korsningar som markerats av Joy, vita cirklar är korsningar som inte markerats av Joy, dubbelcirkeln är korsningen där stadshuset ligger, och siffrorna representerar varje steg.

Joys rörelsebana

I Exempel 1 tillhör de 3 områden som markeras av det skuggade området i figuren nedan Joys revir.

Joys revir i Exempel 1

Indata 2

12 2
EENWSEEESWWS

Utdata 2

7

Förklaring

I Exempel 2 genomförs promenaden under 2 dagar. Varje dags rörelsebana är densamma som i Exempel 1. När promenaden är avslutad tillhör de 7 områden som markeras av det skuggade området i figuren nedan Joys revir.

Joys revir i Exempel 2

Indata 3

7 1
ENNWNNE

Utdata 3

0

Förklaring

I Exempel 3 finns det inga områden som tillhör Joys revir.

Indata 4

16 5
WSESSSWWWEEENNNW

Utdata 4

21