S. 网格路径

Type: Default

2000ms

256MiB

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

翻译自 CSES-1625 题。

对于一个 $7\times 7$ 的网格图，总共有 $88418$ 条不同的路径可以从左上角走到左下角，其中路径经过每个格子恰好一次。每条路径对应一个包含 $48$ 个字符的字符串，字符串由 D（向下）、U（向上）、L（向左）、R（向右）四种字符组成。

例如，下图是一种可能的路径，它所对应的描述字符串为：DRURRRRRDDDLUULDDDLDRRURDDLLLLLURULURRUULDLLDDDD。

![](file://_XoCrrDAT8EmCelk5b13A.png)

你会得到一个包含 ? 的字符串，其中 ? 字符表示这个位置可以放 D、U、L、R 四个方向的任意一个。

请你计算可能的描述路径的字符串数量，使得这条路径可以从左上角到左下角，并且每个格子恰好经过一次。

输入长度为 $48$ 的字符串，字符串由 D、U、L、R 和 ? 共五种字符组成。

输出一行一个整数表示可能的路径数量。

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