I hate Cleaning Robot

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

このロボットに、 種類の文字 L 、R 、U 、D からなる文字列で表されたプログラムが与えられます。

ロボットは、与えられたプログラムの各文字を先頭の文字から順に読み、各文字について以下の行動を行います。

• ロボットの現在地をマス とする
• 読んだ文字に応じて以下の通りに行動する:
  • L を読んだとき: マス に移動する。
  • R を読んだとき: マス に移動する。
  • U を読んだとき: マス に移動する。
  • D を読んだとき: マス に移動する。

「文字 を 個連結したもの」という形式で 個の文字列 が与えられます。ロボットが実行するプログラムは 個の文字列を任意の順序で連結したもののうちいずれかです。

ロボットが一度でも存在したことのあるマス（ロボットの初期位置であるマス を含む）は掃除されます。

以下の条件を満たすマスがいくつあるか求めてください。

• 実行されうるプログラム 通りのうち 通り以上において掃除される。

• は 以上 以下の整数
• は L 、R 、U 、D のいずれか
• は 以上 以下の整数

答えを出力し、最後に改行してください。

2
R 2
D 3

10

RR 、 DDD であるため、実行されるプログラムは RRDDD または DDDRR です。

3
D 3
U 6
D 4

14

8
D 4
R 7
U 7
R 9
D 10
R 9
U 6
L 6

616