题目描述

在一个无限二维网格上，有一个清洁机器人位于平面上的方格 $(0, 0)$。

机器人将接收一个由四种字符 L、R、U、D 组成的字符串表示的程序。
它将从左到右读取程序中的字符，并对读取的每个字符执行以下动作。

1. 设 $(x, y)$ 是机器人当前所处方格的坐标。
2. 根据读取到的字符执行以下移动：
   • 如果读取到 L：移到 $(x-1, y)$。
   • 如果读取到 R：移到 $(x+1, y)$。
   • 如果读取到 U：移到 $(x, y-1)$。
   • 如果读取到 D：移到 $(x, y+1)$。

给定一个字符串 $S$，它由字符 L、R、U、D 组成。机器人执行的程序是 $S$ 的 $K$ 个副本的连接。

机器人至少访问过一次的方格，包括初始位置 $(0, 0)$，将被清洁。
打印程序执行结束后将被清洁的方格数量。

约束条件

• $S$ 是一个长度为 $1$ 到 $2 \times 10^5$（含边界）的字符串，由字符 L、R、U、D 组成。
• $1 \leq K \leq 10^{12}$

输入

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

$S$ $K$

输出

打印程序执行结束后将被清洁的方格数量。

示例输入 1

RDRUL
2

示例输出 1

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

示例输入 2

LR
1000000000000

示例输出 2

2

示例输入 3

UUURRDDDRRRUUUURDLLUURRRDDDDDDLLLLLLU
31415926535

示例输出 3

219911485785