{"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\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 type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eGaius Julius Caesar, một tướng nổi tiếng, thích sắp xếp quân lính của mình. Tổng cộng đội quân có \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e\u003c/span\u003e lính bộ và \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e\u003c/span\u003e kỵ binh. Caesar nghĩ rằng một sắp xếp không đẹp nếu ở đâu đó trong hàng có nhiều hơn \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e\u003c/span\u003e lính bộ đứng liên tiếp, hoặc có nhiều hơn \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e\u003c/span\u003e kỵ binh đứng liên tiếp. Hãy tìm số sắp xếp \u003cspan class\u003d\"tex-font-style-bf\"\u003eđẹp\u003c/span\u003e của quân lính. \u003c/p\u003e\u003cp\u003eLưu ý rằng tất cả \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e + \u003ci\u003en\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e\u003c/span\u003e chiến binh phải có mặt trong mỗi sắp xếp. Tất cả lính bộ được coi là không thể phân biệt được với nhau. Tương tự, tất cả kỵ binh được coi là không thể phân biệt được với nhau.\u003c/p\u003e"}},{"title":"Nhập","value":{"format":"HTML","content":"\u003cp\u003eDòng duy nhất chứa bốn số nguyên cách nhau bởi dấu cách \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003en\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e\u003c/span\u003e, \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e\u003c/span\u003e (\u003cspan class\u003d\"tex-span\"\u003e1 ≤ \u003ci\u003en\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003en\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e ≤ 100, 1 ≤ \u003ci\u003ek\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e, \u003ci\u003ek\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e ≤ 10\u003c/span\u003e) đại diện cho số lính bộ và kỵ binh, và số lớn nhất chấp nhận được của lính bộ và kỵ binh đứng liên tiếp, tương ứng.\u003c/p\u003e"}},{"title":"Đầu ra","value":{"format":"HTML","content":"\u003cp\u003eIn ra số sắp xếp đẹp của đội quân theo modulo \u003cspan class\u003d\"tex-span\"\u003e100000000\u003c/span\u003e \u003cspan class\u003d\"tex-span\"\u003e(10\u003csup class\u003d\"upper-index\"\u003e8\u003c/sup\u003e)\u003c/span\u003e. Đó là, in ra số cách sắp xếp quân lính, mà không có nhiều hơn \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e1\u003c/sub\u003e\u003c/span\u003e lính bộ đứng liên tiếp, và không có nhiều hơn \u003cspan class\u003d\"tex-span\"\u003e\u003ci\u003ek\u003c/i\u003e\u003csub class\u003d\"lower-index\"\u003e2\u003c/sub\u003e\u003c/span\u003e kỵ binh đứng liên tiếp.\u003c/p\u003e"}},{"title":"Ví dụ 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\u003e2 1 1 10\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"}},{"title":"Ví dụ 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\u003e2 3 1 2\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"}},{"title":"Ví dụ 3","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\u003e2 4 1 1\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"}},{"title":"Lưu ý","value":{"format":"HTML","content":"\u003cp\u003eHãy đánh dấu một lính bộ là \u003cspan class\u003d\"tex-font-style-tt\"\u003e1\u003c/span\u003e, và một kỵ binh là \u003cspan class\u003d\"tex-font-style-tt\"\u003e2\u003c/span\u003e.\u003c/p\u003e\u003cp\u003eTrong ví dụ thứ nhất, chỉ có một sắp xếp đẹp là: \u003cspan class\u003d\"tex-font-style-tt\"\u003e121\u003c/span\u003e\u003c/p\u003e\u003cp\u003eTrong ví dụ thứ hai, có 5 sắp xếp đẹp: \u003cspan class\u003d\"tex-font-style-tt\"\u003e12122\u003c/span\u003e, \u003cspan class\u003d\"tex-font-style-tt\"\u003e12212\u003c/span\u003e, \u003cspan class\u003d\"tex-font-style-tt\"\u003e21212\u003c/span\u003e, \u003cspan class\u003d\"tex-font-style-tt\"\u003e21221\u003c/span\u003e, \u003cspan class\u003d\"tex-font-style-tt\"\u003e22121\u003c/span\u003e\u003c/p\u003e"}}]}