{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch1\u003e問題名 箱根駅伝\u003c/h1\u003e\n\u003cp\u003e日本のお正月の風物詩に箱根駅伝があります。箱根駅伝は、各チーム 10 人の走者が中継所ごとに襷をつなぎながらゴールを目指すというものです。テレビの放送では中継所で各チームの通過順位と共に前の中継所からの順位変動が表示されます。そこで、それを見て前の中継所の各チームの通過順として考えられるものが何通りあるか答えてください。ありえた通過順の数は非常に大きくなりうるので、1,000,000,007 で割った余りで答えて下さい。\n\u003c/p\u003e\n\u003ch2\u003eInput\u003c/h2\u003e\n\u003cp\u003e入力は以下の形で与えられます\n\u003c/p\u003e\u003cblockquote\u003e\n\u003cvar\u003en\u003c/var\u003e\u003cbr\u003e\u003cvar\u003ec\u003csub\u003e1\u003c/sub\u003e\u003c/var\u003e\u003cbr\u003e\u003cvar\u003ec\u003csub\u003e2\u003c/sub\u003e\u003c/var\u003e\u003cbr\u003e...\u003cbr\u003e\u003cvar\u003ec\u003csub\u003en\u003c/sub\u003e\u003c/var\u003e\u003cbr\u003e\u003c/blockquote\u003e\n\u003cp\u003e1行目にはチーム数を表す数字 \u003cvar\u003en\u003c/var\u003e (\u003cvar\u003e1 ≤ n ≤ 200\u003c/var\u003e) が、続く \u003cvar\u003en\u003c/var\u003e 行には 1 位から順に前の中継所からの順位変動 \u003cvar\u003ec\u003csub\u003ei\u003c/sub\u003e\u003c/var\u003e (\u0027\u003ccode\u003eD\u003c/code\u003e\u0027 なら順位が落ちてる、\u0027\u003ccode\u003eU\u003c/code\u003e\u0027 なら順位が上がってる、\u0027\u003ccode\u003e-\u003c/code\u003e\u0027 なら順位が変わってない) が書いてあります。\n\u003c/p\u003e\n\u003ch2\u003eOutput\u003c/h2\u003e\n\u003cp\u003e前の中継所でありえた通過順が何通りかを、 1,000,000,007 で割ったあまりで 1 行で出力して下さい。\n\u003c/p\u003e\n\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\u003e3\n-\nU\nD\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\u003cp\u003eこの中継所を 1 位、 2 位、 3 位で通過したチームのチーム名をそれぞれ A, B, C とすると、前の中継所の通過順として考えられるのは 1 位:チーム A, 2 位:チーム C, 3 位:チーム B の 1 通りのみです。\n\u003c/p\u003e\n\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\u003e5\nU\nU\n-\nD\nD\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\u003cp\u003eこの中継所の通過順にチーム名を A, B, C, D, E とすると、前の中継所の通過順として考えられるのは {D, E, C, A, B}, {D, E, C, B, A}, {E, D, C, A, B}, {E, D, C, B, A}, {D, A, C, E, B} の5通りです。\n\u003c/p\u003e\n\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\u003e8\nU\nD\nD\nD\nD\nD\nD\nD\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n\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\u003e10\nU\nD\nU\nD\nU\nD\nU\nD\nU\nD\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e608\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n\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\u003e2\nD\nU\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n"}}]}