题目思路

经典的海拔高度统计模型。观察到题目数据只有 $2000$ , 那么考虑动态规划:

$dp_{i,j}$ 代表填完前i个移动，并且上坡次数比下坡次数多 $j$ 个的方案数。最后的答案是 $dp_{n,0}$

为什么要这么定义:一个合法的移动序列，它的充分必要条件是:每个前缀的上坡次数都不少于下坡次数（即海拔始终非负），且整体的上坡次数 = 下坡次数（最终回到海拔0）

转移就很简单了:

题目内容

探险家在峡谷中记录了自己的移动轨迹，每次移动要么是上坡（U），要么是下坡（D）。记录中存在部分模糊不清的标记，用 ? 表示，每个 ? 可以独立地替换为 U 或 D。

你需要计算有多少种替换方案，使得从海拔 $0$ 出发，依次执行这些移动后，最终回到海拔 $0$ ，并且途中任意时刻的海拔高度均不小于 $0$ 。

答案可能很大，请输出其对 $10^9+7$ 取模的结果。

字符串的长度不超过 $2000$ 。