{"trustable":true,"prependHtml":"\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS-MML_HTMLorMML\" type\u003d\"text/javascript\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"panel_content\"\u003e排列的签名是根据以下方法计算的字符串:对于排列的每对连续元素,如果第二个元素大于第一个元素,则写下字母\u0027I\u0027(增加),否则写下字母\u0027D\u0027(减少)。例如,排列{3,1,2,7,4,6,5}的签名是\"DIIDID\"。\u003cbr\u003e\u003cbr\u003e你的任务如下:给定描述许多可能排列的签名的字符串,找出满足此签名的排列有多少个。\u003cbr\u003e\u003cbr\u003e注意:对于任何正整数n,n个元素的排列是一个长度为n的序列,其中包含1到n的每个整数各一次。\u003cbr\u003e\u003c/div\u003e"}},{"title":"输入","value":{"format":"HTML","content":"每个测试用例由一个长度为1到1000个字符的字符串组成,只包含字母\u0027I\u0027、\u0027D\u0027或\u0027?\u0027,表示一个排列签名。\u003cbr\u003e\u003cbr\u003e每个测试用例占据一行,没有前导或尾随空格。\u003cbr\u003e\u003cbr\u003e进行到文件末尾。这些字符串中的\u0027?\u0027可以是\u0027I\u0027或\u0027D\u0027。\u003cbr\u003e"}},{"title":"输出","value":{"format":"HTML","content":"对于每个测试用例,将满足签名的排列数量打印在一行上。如果结果太大,以模1000000007的方式打印余数。\u003cbr\u003e"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003eII\r\nID\r\nDI\r\nDD\r\n?D\r\n??\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n2\r\n2\r\n1\r\n3\r\n6\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"提示","value":{"format":"HTML","content":"\u003cbr\u003e排列{1,2,3}的签名是\"II\"。\u003cbr\u003e排列{1,3,2}和{2,3,1}的签名是\"ID\"。\u003cbr\u003e排列{3,1,2}和{2,1,3}的签名是\"DI\"。\u003cbr\u003e排列{3,2,1}的签名是\"DD\"。\u003cbr\u003e\"?D\"可以是\"ID\"或\"DD\"。\u003cbr\u003e\"??\"给出长度为3的所有可能排列。\u003cbr\u003e"}}]}