{"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\u003eNeko đang chơi với đồ chơi của mình ở sân sau nhà của Aki. Aki quyết định chơi một trò đùa với anh ta, bằng cách lén đặt cỏ mèo vào đồ chơi của Neko. Thật không may, anh ta đã quá đà và đặt cả một túi cỏ mèo vào những đồ chơi...\u003c/p\u003e\u003cp\u003eNeko mất cả một ngày để trở lại bình thường. Neko báo cáo với Aki rằng anh ta đã thấy rất nhiều điều kỳ lạ, bao gồm một \u003ca href\u003d\"https://en.wikipedia.org/wiki/Trie\"\u003etrie\u003c/a\u003e của tất cả các chuỗi dấu ngoặc đúng có độ dài $$$2n$$$.\u003c/p\u003e\u003cp\u003eĐịnh nghĩa của chuỗi dấu ngoặc đúng như sau:\u003c/p\u003e\u003cul\u003e \u003cli\u003e Chuỗi rỗng là một chuỗi dấu ngoặc đúng, \u003c/li\u003e\u003cli\u003e Nếu $$$s$$$ là một chuỗi dấu ngoặc đúng, thì $$$(\\,s\\,)$$$ cũng là một chuỗi dấu ngoặc đúng, \u003c/li\u003e\u003cli\u003e Nếu $$$s$$$ và $$$t$$$ là chuỗi dấu ngoặc đúng, thì $$$st$$$ cũng là một chuỗi dấu ngoặc đúng. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eVí dụ, các chuỗi \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e(())\u003c/span\u003e\", \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e()()\u003c/span\u003e\" tạo thành một chuỗi dấu ngoặc đúng, trong khi \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e)(\u003c/span\u003e\" và \"\u003cspan class\u003d\"tex-font-style-tt\"\u003e((\u003c/span\u003e\" không.\u003c/p\u003e\u003cp\u003eSau đó, Aki đưa ra một vấn đề thú vị: Kích thước của sự phù hợp tối đa (tập hợp lớn nhất các cạnh sao cho không có hai cạnh nào có một đỉnh chung) trong trie này là bao nhiêu? Vì câu trả lời có thể rất lớn, in nó theo modulo $$$10^9 + 7$$$.\u003c/p\u003e"}},{"title":"Nhập","value":{"format":"HTML","content":"\u003cp\u003eDòng duy nhất chứa một số nguyên $$$n$$$ ($$$1 \\le n \\le 1000$$$).\u003c/p\u003e"}},{"title":"Đầu ra","value":{"format":"HTML","content":"\u003cp\u003eIn chính xác một số nguyên\u0026nbsp;— kích thước của sự phù hợp tối đa trong trie. Vì câu trả lời có thể rất lớn, in nó theo modulo $$$10^9 + 7$$$.\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\u003e1\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\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\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\u003e3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e9\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"Ghi chú","value":{"format":"HTML","content":"\u003cp\u003eCác hình ảnh dưới đây minh họa cho các trie trong hai ví dụ đầu tiên (để rõ ràng, dấu ngoặc tròn được thay thế bằng dấu ngoặc vuông). Sự phù hợp tối đa được đánh dấu màu xanh.\u003c/p\u003e\u003ccenter\u003e \u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/6e3593cf0d0ec4166901b6b5370f4547?v\u003d1711178279\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e\u0026nbsp;\u003cimg class\u003d\"tex-graphics\" src\u003d\"CDN_BASE_URL/46aacaf50ec5a4d252d145add5475169?v\u003d1711178279\" style\u003d\"max-width: 100.0%;max-height: 100.0%;\"\u003e \u003c/center\u003e"}}]}