在一个 7×7 的网格中,从左上角的方格到左下角的方格共有 88418 条路径。每条路径对应一个由 48 个字符组成的描述,包含字符 D(下)、U(上)、L(左)和 R(右)。 例如,路径对应的描述为 DRURRRRRDDDLUULDDDLDRRURDDLLLLLURULURRUULDLLDDDD。 给你一个路径的描述,其中也可能包含字符 ?(任意方向)。你的任务是计算与描述相匹配的路径数量。

输入格式

唯一的输入行是一个由 48 个字符组成的字符串,包含字符 ?、D、U、L 和 R。

输出格式

输出一个整数:总路径的数量。

??????R??????U??????????????????????????LD????D?

201