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。


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

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

输入格式

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

输出格式

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

样例

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

201