{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"An integer number is called _good_ if it consists of _good_ digits.\r\n\r\nYou are given **n** intervals [`l[i]`, `r[i]`] and the set of digits which are considered _good_. Find how many ways there are to choose one integer from each of those intervals so that their sum will be a _good_ number. You can choose the same number in multiple intervals. Two ways are considered different if there exists an integer **i** (**1** ≤ **i** ≤ **n**) such that different integers are chosen from interval **i**. The answer may be large, so you have to give it modulo `10^9` + **7**.\r\n\r\n#### Input\r\nThe first line contains ten integers: **i**-th of them is equal to **1** if digit **i** is good and **0** otherwise. These integers are numbered from **0** to **9**. The next line contains a single integer **n** (**1** ≤ **n** ≤ **7**): the number of intervals. Next **n** lines contain two integers each without leading zeros: `l[i]` and `r[i]` (**0** ≤ `l[i]` ≤ `r[i]` \u003c `10^10`).\r\n\r\n#### Output\r\nPrint the number of ways modulo `10^9` + **7**."}},{"title":"Example","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 1 1 1 1 1 1 1 1 1\n2\n4 6\n15 19\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e15\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr\u003e\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 0 1 0 1 0 1 0 0 0\n2\n4 6\n15 19\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e7\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr\u003e\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 0 0 1 1 1 1 1 1 1\n2\n4 6\n15 19\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"}}]}