网格路径描述 (Task 1625)

• 链接: https://cses.fi/problemset/task/1625
• 板块: Introductory Problems
• 时限: 1.00 s ｜ 内存: 512 MB

描述

在一个 $7 \times 7$ 的网格中，从左上角格子到左下角格子共有 $88418$ 条路径。每条路径对应一个由 $48$ 个字符组成的描述，字符包括 D（下）、U（上）、L（左）和 R（右）。（图示见原页：https://cses.fi/file/3624b569007eb03818b6611755f1bdbe4cdbd0a8334baf9fedc5365914bdd661 ）例如，图中的路径对应的描述为 DRURRRRRDDDLUULDDDLDRRURDDLLLLLURULURRUULDLLDDDD。给定一个路径描述，其中也可能包含字符 ?（表示任意方向）。你的任务是计算与该描述匹配的路径数量。

输入

输入仅一行，包含一个由 ?、D、U、L 和 R 组成的 $48$ 字符字符串。

输出

打印一个整数：路径的总数。

约束

• 输入字符串长度固定为 $48$
• 字符集为 ?, D, U, L, R

样例

输入：
??????R??????U??????????????????????????LD????D?
输出：
201

来源：CSES Problem Set（英文原文，LaTeX 公式以源码保留）。隐藏测试用例不公开，仅含页面展示的样例 I/O。