清洁机器人

题目描述

在无限二维网格的方格 $(0, 0)$ 处有一个清洁机器人。

机器人将被赋予一个由 L、R、U、D 四种字符组成的程序字符串。

它从左到右读取程序中的字符，并对每个读取到的字符执行以下动作。

设 $(x, y)$ 为机器人当前所在的方格。

根据读取到的字符进行移动：

• 读到 L：移动到 $(x-1, y)$。
• 读到 R：移动到 $(x+1, y)$。
• 读到 U：移动到 $(x, y-1)$。
• 读到 D：移动到 $(x, y+1)$。

给定一个由 L、R、U、D 组成的字符串 $S$。 机器人将要执行的程序是 $K$ 个 $S$ 的拼接。

机器人至少经过一次的方格（包括初始位置 $(0, 0)$）将被清洁。

输出程序执行结束时被清洁的方格数。

输入格式

输入按以下格式从标准输入给出：

$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)$。

LR
1000000000000

2

UUURRDDDRRRUUUURDLLUURRRDDDDDDLLLLLLU
31415926535

219911485785

数据范围

• $S$ 是由 L、R、U、D 组成的字符串，长度在 $1$ 到 $2 \times 10^5$（含）之间
• $1 \le K \le 10^{12}$