题目描述

無限に広がる二次元グリッドのマス $(0,\ 0)$ に掃除ロボットが置かれています。

このロボットに、$4$ 種類の文字 L 、R 、U 、D からなる文字列で表されたプログラムが与えられます。
ロボットは、与えられたプログラムの各文字を先頭の文字から順に読み、各文字について以下の行動を行います。

1. ロボットの現在地をマス $(x,\ y)$ とする
2. 読んだ文字に応じて以下の通りに移動する:

• L を読んだとき: マス $(x-1,\ y)$ に移動する。
• R を読んだとき: マス $(x+1,\ y)$ に移動する。
• U を読んだとき: マス $(x,\ y-1)$ に移動する。
• D を読んだとき: マス $(x,\ y+1)$ に移動する。

L 、R 、U 、D からなる文字列 $S$ が与えられます。 ロボットが実行するプログラムは、文字列 $S$ を $K$ 個連接したものです。

ロボットが一度でも存在したことのあるマス（ロボットの初期位置であるマス $(0,\ 0)$ を含む）は掃除されます。
ロボットがプログラムの実行を終えた後の時点で、掃除されているマスの個数を出力して下さい。

输入格式

入力は以下の形式で標準入力から与えられる。

$S$ $K$

输出格式

ロボットがプログラムの実行を終えた後の時点で、掃除されているマスの個数を出力せよ。

RDRUL
2

7

LR
1000000000000

2

UUURRDDDRRRUUUURDLLUURRRDDDDDDLLLLLLU
31415926535

219911485785

提示

制約

• $S$ は L 、R 、U 、D からなる長さ $1$ 以上 $2\ \times\ 10^5$ 以下の文字列
• $1\ \leq\ K\ \leq\ 10^{12}$

Sample Explanation 1

ロボットが実行するプログラムは RDRULRDRUL です。ロボットは初期位置であるマス $(0,\ 0)$ からはじめ、 $ (0,\ 0)\ \rightarrow\ (1,\ 0)\ \rightarrow\ (1,\ 1)\ \rightarrow\ (2,\ 1)\ \rightarrow\ (2,\ 0)\ \rightarrow\ (1,\ 0)\ \rightarrow\ (2,\ 0)\ \rightarrow\ (2,\ 1)\ \rightarrow\ (3,\ 1)\ \rightarrow\ (3,\ 0)\ \rightarrow\ (2,\ 0) $ と移動します。 その後掃除されているマスは、$ (0,\ 0),\ (1,\ 0),\ (1,\ 1),\ (2,\ 0),\ (2,\ 1),\ (3,\ 0),\ (3,\ 1) $ の $7$ 個です。