{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003ch3\u003e Read problems statements in \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/COOK65/mandarin/CHEFVEC.pdf\"\u003eMandarin Chinese\u003c/a\u003e, \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/COOK65/russian/CHEFVEC.pdf\"\u003eRussian\u003c/a\u003e and \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/COOK65/vietnamese/CHEFVEC.pdf\"\u003eVietnamese\u003c/a\u003e as well.\u003c/h3\u003e\n\n\n\u003cp\u003e\nChef has an integer array \u003cb\u003eX\u003c/b\u003e, and a binary array \u003cb\u003eS\u003c/b\u003e, both of size \u003cb\u003eN\u003c/b\u003e. He wants to know how many vectors (denote by \u003cb\u003eV\u003c/b\u003e) of \u003cb\u003eN\u003c/b\u003e elements exist, for which the following conditions hold for all valid indices \u003cb\u003ei\u003c/b\u003e (that is, for all 1 ≤ \u003cb\u003ei\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e).\n\u003cli\u003e0 ≤ \u003cb\u003eV\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e \u003c 10\u003csup\u003e18\u003c/sup\u003e\u003c/li\u003e\n\u003cli\u003eIf \u003cb\u003eS\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e \u003d 1, \u003cb\u003eV\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e is ≥ \u003cb\u003eX\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, and if \u003cb\u003eS\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e \u003d 0, \u003cb\u003eV\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e ≤ \u003cb\u003eX\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e\u003c/li\u003e\n\u003cli\u003eSum of the elements of \u003cb\u003eV\u003c/b\u003e, when viewed as a string, contains \"47\" as a substring.\u003c/li\u003e\n\u003c/p\u003e\n\u003cp\u003e\nPlease help Chef find this count. Since it may be a very large number, you should output the count modulo \u003cb\u003e10\u003csup\u003e9\u003c/sup\u003e+7\u003c/b\u003e.\n\u003c/p\u003e\n\n\u003ch3\u003eInput\u003c/h3\u003e\nThe first line of input contains one integer \u003cb\u003eN\u003c/b\u003e. The next \u003cb\u003eN\u003c/b\u003e lines contain two integers each, with the \u003cb\u003ei\u003csup\u003eth\u003c/sup\u003e\u003c/b\u003e containing \u003cb\u003eS\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e and \u003cb\u003eX\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e. If \u003cb\u003eS\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e \u003d 0, then \u003cb\u003eV\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e ≤ \u003cb\u003eX\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e, otherwise \u003cb\u003eV\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e ≥ \u003cb\u003eX\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e.\n\n\u003ch3\u003eOutput\u003c/h3\u003e\nOutput a single line containing a single integer — the answer to Chef\u0027s problem modulo \u003cb\u003e10\u003csup\u003e9\u003c/sup\u003e\u003c/b\u003e+\u003cb\u003e7\u003c/b\u003e.\n\n\u003ch3\u003eConstraints\u003c/h3\u003e\n\u003cul\u003e\n\u003cli\u003e1 ≤ \u003cb\u003eN\u003c/b\u003e ≤ 8\u003c/li\u003e\n\u003cli\u003e0 ≤ \u003cb\u003eX\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e \u003c 10\u003csup\u003e18\u003c/sup\u003e\u003c/li\u003e\n\u003cli\u003e\u003cb\u003eS\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e is either 0 or 1. \u003c/li\u003e\n\u003c/ul\u003e\n\n\u003ch3\u003eExample\u003c/h3\u003e\n\u003cpre\u003e\n\u003cb\u003eInput:\u003c/b\u003e\n\u003ctt\u003e2\n0 22\n0 30\n\u003c/tt\u003e\n\u003cb\u003eOutput:\u003c/b\u003e\n\u003ctt\u003e6\n\u003c/tt\u003e\n\u003c/pre\u003e\n\n\u003ch3\u003eExplanation:\u003c/h3\u003e\n\u003cp\u003e\nThere are 6 such vectors: (17, 30), (18, 29), (19, 28), (20, 27), (21, 26), (22, 25).\n\u003c/p\u003e"}}]}