{"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\u003eBeing bored of exploring the Moon over and over again Wall-B decided to explore something he is made of — binary numbers. He took a binary number and decided to count how many times different substrings of length two appeared. He stored those values in $$$c_{00}$$$, $$$c_{01}$$$, $$$c_{10}$$$ and $$$c_{11}$$$, representing how many times substrings \u003cspan class\u003d\"tex-font-style-tt\"\u003e00\u003c/span\u003e, \u003cspan class\u003d\"tex-font-style-tt\"\u003e01\u003c/span\u003e, \u003cspan class\u003d\"tex-font-style-tt\"\u003e10\u003c/span\u003e and \u003cspan class\u003d\"tex-font-style-tt\"\u003e11\u003c/span\u003e appear in the number respectively. For example:\u003c/p\u003e\u003cp\u003e $$$10111100 \\rightarrow c_{00} \u003d 1, \\ c_{01} \u003d 1,\\ c_{10} \u003d 2,\\ c_{11} \u003d 3$$$\u003c/p\u003e\u003cp\u003e $$$10000 \\rightarrow c_{00} \u003d 3,\\ c_{01} \u003d 0,\\ c_{10} \u003d 1,\\ c_{11} \u003d 0$$$\u003c/p\u003e\u003cp\u003e $$$10101001 \\rightarrow c_{00} \u003d 1,\\ c_{01} \u003d 3,\\ c_{10} \u003d 3,\\ c_{11} \u003d 0$$$\u003c/p\u003e\u003cp\u003e $$$1 \\rightarrow c_{00} \u003d 0,\\ c_{01} \u003d 0,\\ c_{10} \u003d 0,\\ c_{11} \u003d 0$$$\u003c/p\u003e\u003cp\u003eWall-B noticed that there can be multiple binary numbers satisfying the same $$$c_{00}$$$, $$$c_{01}$$$, $$$c_{10}$$$ and $$$c_{11}$$$ constraints. Because of that he wanted to count how many binary numbers satisfy the constraints $$$c_{xy}$$$ given the interval $$$[A, B]$$$. Unfortunately, his processing power wasn\u0027t strong enough to handle large intervals he was curious about. Can you help him? Since this number can be large print it modulo $$$10^9 + 7$$$.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eFirst two lines contain two positive binary numbers $$$A$$$ and $$$B$$$ ($$$1 \\leq A \\leq B \u0026lt; 2^{100\\,000}$$$), representing the start and the end of the interval respectively. Binary numbers $$$A$$$ and $$$B$$$ have no leading zeroes.\u003c/p\u003e\u003cp\u003eNext four lines contain decimal numbers $$$c_{00}$$$, $$$c_{01}$$$, $$$c_{10}$$$ and $$$c_{11}$$$ ($$$0 \\leq c_{00}, c_{01}, c_{10}, c_{11} \\leq 100\\,000$$$) representing the count of two-digit substrings \u003cspan class\u003d\"tex-font-style-tt\"\u003e00\u003c/span\u003e, \u003cspan class\u003d\"tex-font-style-tt\"\u003e01\u003c/span\u003e, \u003cspan class\u003d\"tex-font-style-tt\"\u003e10\u003c/span\u003e and \u003cspan class\u003d\"tex-font-style-tt\"\u003e11\u003c/span\u003e respectively. \u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput one integer number representing how many binary numbers in the interval $$$[A, B]$$$ satisfy the constraints mod $$$10^9 + 7$$$.\u003c/p\u003e"}},{"title":"Examples","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\u003e10\n1001\n0\n0\n1\n1\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"}},{"title":"","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\u003e10\n10001\n1\n2\n3\n4\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"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eExample 1: The binary numbers in the interval $$$[10,1001]$$$ are $$$10,11,100,101,110,111,1000,1001$$$. Only number 110 satisfies the constraints: $$$c_{00} \u003d 0, c_{01} \u003d 0, c_{10} \u003d 1, c_{11} \u003d 1$$$.\u003c/p\u003e\u003cp\u003eExample 2: No number in the interval satisfies the constraints\u003c/p\u003e"}}]}