{"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\"\u003eDominoes are rectangular tiles with nice 2 × 1 and 1 × 2 sizes.\u003cbr\u003e\u003cbr\u003eThe tiling is called solid if it is not possible to split the tiled rectangle by a straight line, not crossing the interior of any tile. For example, on the picture below the tilings (a) and (b) are solid, while the tilings (c) and (d) are not.\u003cbr\u003e\u003cbr\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/7d6b8a036b23602910a664c46eea6517?v\u003d1726298468\"\u003e\u003cbr\u003e\u003cbr\u003eNow the managers of the company wonder, how many different solid tilings exist for an m × n rectangle. Help them to find that out.\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"The input file contains $m$ and $n (1 \\leq m, n \\leq 16)$."}},{"title":"Output","value":{"format":"HTML","content":"Output one integer number \u003cb\u003emod 1e9+7\u003c/b\u003e - the number of solid tilings of m×n rectangle with 2 × 1 and 1 × 2 pavement tiles."}},{"title":"Sample","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 2\r\n5 6\r\n8 7\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e0\r\n6\r\n13514\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Hint","value":{"format":"HTML","content":"\u003cbr\u003eAll solid tilings for the 5×6 rectangle are provided on the picture below:\u003cbr\u003e\u003cimg style\u003d\"max-width:100%;\" src\u003d\"CDN_BASE_URL/0e67c5931d653c6e87b0951ab0751676?v\u003d1726298468\"\u003e\u003cbr\u003e"}}]}