{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e波利卡普斯玩红色和蓝色弹珠。他把从左到右排成一行的\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e个弹珠。结果,这些弹珠形成了一个\u003cspan class\u003d\"tex-font-style-it\"\u003e斑马纹\u003c/span\u003e。\u003c/p\u003e\u003cp\u003e一个非空的红色和蓝色弹珠序列被称为\u003cspan class\u003d\"tex-font-style-it\"\u003e斑马纹\u003c/span\u003e,如果这个序列中弹珠的颜色交替。例如,序列(\u003cspan class\u003d\"tex-font-style-tt\"\u003e红色;蓝色;红色\u003c/span\u003e)和(\u003cspan class\u003d\"tex-font-style-tt\"\u003e蓝色\u003c/span\u003e)是斑马纹,而序列(\u003cspan class\u003d\"tex-font-style-tt\"\u003e红色;红色\u003c/span\u003e)不是斑马纹。\u003c/p\u003e\u003cp\u003e现在波利卡普斯想知道,从这个序列中挑选一个斑马纹\u003cspan class\u003d\"tex-font-style-bf\"\u003e子序列\u003c/span\u003e有多少种方式。帮助他解决这个问题,找出答案在模\u003cspan class\u003d\"tex-span\"\u003e1000000007\u003c/span\u003e\u003cspan class\u003d\"tex-span\"\u003e(10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e + 7)\u003c/span\u003e下的余数。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e第一行包含一个整数\u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003c/span\u003e\u003cspan class\u003d\"tex-span\"\u003e(1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 10\u003csup class\u003d\"upper-index\"\u003e6\u003c/sup\u003e)\u003c/span\u003e — 波利卡普斯序列中弹珠的数量。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e输出一个数字 — 问题的答案在模\u003cspan class\u003d\"tex-span\"\u003e1000000007\u003c/span\u003e\u003cspan class\u003d\"tex-span\"\u003e(10\u003csup class\u003d\"upper-index\"\u003e9\u003c/sup\u003e + 7)\u003c/span\u003e下的余数。\u003c/p\u003e"}},{"title":"示例1","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\u003e3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"示例2","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\u003e4\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e11\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"注意","value":{"format":"HTML","content":"\u003cp\u003e让我们考虑第一个测试样例。假设波利卡普斯最初有序列(\u003cspan class\u003d\"tex-font-style-tt\"\u003e红色;蓝色;红色\u003c/span\u003e),那么有六种方式选择一个斑马纹:\u003c/p\u003e\u003cul\u003e\u003cli\u003e选择第一个弹珠;\u003c/li\u003e\u003cli\u003e选择第二个弹珠;\u003c/li\u003e\u003cli\u003e选择第三个弹珠;\u003c/li\u003e\u003cli\u003e选择第一个和第二个弹珠;\u003c/li\u003e\u003cli\u003e选择第二个和第三个弹珠;\u003c/li\u003e\u003cli\u003e选择第一个、第二个和第三个弹珠。\u003c/li\u003e\u003c/ul\u003e\u003cp\u003e可以证明,如果波利卡普斯选择(\u003cspan class\u003d\"tex-font-style-tt\"\u003e蓝色;红色;蓝色\u003c/span\u003e)作为初始序列,选择的方式数量不会改变。\u003c/p\u003e"}}]}