Một thành phố có vô số đường thẳng song song theo hướng bắc-nam và đông-tây, khoảng cách giữa hai đường kề nhau là 1 km. Tòa thị chính ở giao lộ \((0,0)\); giao lộ \((i,j)\) nằm cách đó \(i\) km về đông và \(j\) km về bắc, với giá trị âm chỉ hướng ngược lại.

Một chú chó tên Joy lập kế hoạch đi dạo trong \(K\) ngày:

• Sáng ngày đầu, Joy ở \((0,0)\) và đánh dấu giao lộ này.
• Mỗi trưa, Joy thực hiện cùng một chuỗi \(N\) bước. Mỗi bước đi tới một giao lộ kề cạnh và đánh dấu nơi tới.
• Sau chuỗi bước, Joy ngủ tại vị trí hiện tại tới sáng hôm sau.

Ô vuông có bốn đỉnh \((a,b),(a+1,b),(a+1,b+1),(a,b+1)\) thuộc lãnh thổ của Joy nếu cả bốn giao lộ đều đã được đánh dấu ít nhất một lần. Hãy tính số ô thuộc lãnh thổ sau \(K\) ngày.

Dữ liệu vào

• Dòng 1 chứa \(N,K\).
• Dòng 2 chứa xâu \(S\) dài \(N\). Ký tự thứ \(p\) là E, N, W, hoặc S, tương ứng đi sang đông, bắc, tây, nam ở bước \(p\).

Dữ liệu ra

In ra số ô thuộc lãnh thổ của Joy.

Ràng buộc

• \(1\le N\le100000\).
• \(1\le K\le10^9\).

Phân nhóm

• Nhóm 1 (5 điểm): \(N\le50\), \(K=1\).
• Nhóm 2 (10 điểm): \(K=1\).
• Nhóm 3 (23 điểm): \(N\le50\).
• Nhóm 4 (62 điểm): không có ràng buộc bổ sung.

Ví dụ

12 1
EENWSEEESWWS

3

12 2
EENWSEEESWWS

7

7 1
ENNWNNE

0

16 5
WSESSSWWWEEENNNW

21

Nguồn

Kỳ thi chung kết Olympic Tin học Nhật Bản 2015/2016, bài 4.