配点 : $500$ 点

問題文

無限に広がる二次元グリッドのマス $(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$ は L 、R 、U 、D からなる長さ $1$ 以上 $2 \times 10^5$ 以下の文字列
• $1 \leq K \leq 10^{12}$

入力

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

$S$

$K$

出力

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

RDRUL
2

7

ロボットが実行するプログラムは 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$ 個です。

LR
1000000000000

2

UUURRDDDRRRUUUURDLLUURRRDDDDDDLLLLLLU
31415926535

219911485785