数字串 Number String
题意翻译
对于任意一个只含数字 $1$~$n$ 的有序数字串 $\{a_1,a_2,\cdots,a_n\}$，比较数字串中所有相邻数字的大小，后者大于前者的用 `I` 表示，否则用 `D` 表示。例如，数字串 $\{3,1,2,7,4,6,5\}$, $\{2,1,3,7,4,6,5\}$ 和 $\{3,1,2,7,5,6,4\}$ 就表示为 `DIIDID`。`?` 则表示两数的关系未知。例如，`?D` 既有可能是 `ID`，也有可能是`DD`。现给出数字串的表达方式，请输出所有数字串的个数。
为避免数据过大，答案对 $1000000007$ 取模后输出。
题目描述
[problemUrl]: https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=825&page=show_problem&problem=4525
[PDF](https://uva.onlinejudge.org/external/16/p1650.pdf)