{"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/COOK80/mandarin/INCXOR.pdf\"\u003eMandarin Chinese\u003c/a\u003e, \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/COOK80/russian/INCXOR.pdf\"\u003eRussian\u003c/a\u003e and \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/COOK80/vietnamese/INCXOR.pdf\"\u003eVietnamese\u003c/a\u003e as well.\u003c/h3\u003e\n\n\u003cp\u003e \nYou are given a sequence of \u003cb\u003en\u003c/b\u003e integers \u003cb\u003ea\u003c/b\u003e\u003csub\u003e1\u003c/sub\u003e, ..., \u003cb\u003ea\u003c/b\u003e\u003csub\u003e\u003cb\u003en\u003c/b\u003e\u003c/sub\u003e.\nCount the number of sequences b \u003d b\u003csub\u003e1\u003c/sub\u003e, ..., b\u003csub\u003e\u003cb\u003en\u003c/b\u003e\u003c/sub\u003e such that: 0 ≤ b\u003csub\u003e1\u003c/sub\u003e ≤ ... ≤ b\u003csub\u003e\u003cb\u003en\u003c/b\u003e\u003c/sub\u003e \u003c 2\u003csup\u003e31\u003c/sup\u003e and (\u003cb\u003ea\u003c/b\u003e\u003csub\u003e1\u003c/sub\u003e XOR b\u003csub\u003e1\u003c/sub\u003e) ≤ … ≤ (\u003cb\u003ea\u003c/b\u003e\u003csub\u003e\u003cb\u003en\u003c/b\u003e\u003c/sub\u003e XOR b\u003csub\u003e\u003cb\u003en\u003c/b\u003e\u003c/sub\u003e).\nReturn this count, modulo 10\u003csup\u003e9\u003c/sup\u003e+7.\n\u003c/p\u003e\n\n\u003cp\u003e\nHere XOR denotes the \u003ca href\u003d\"https://en.wikipedia.org/wiki/Bitwise_operation#XOR\"\u003ebitwise XOR\u003c/a\u003e.\n\u003c/p\u003e\n\n\n\u003ch3\u003eInput\u003c/h3\u003e\n\u003cp\u003e\nThe first line of input will contain an integer \u003cb\u003eT\u003c/b\u003e, the number of test cases.\n\u003c/p\u003e\n\n\u003cp\u003e\nEach test case will be in two lines.\n\u003c/p\u003e\n\n\u003cp\u003e\nThe first line of the case will contain an integer \u003cb\u003en\u003c/b\u003e.\n\u003c/p\u003e\n\n\u003cp\u003e\nThe next line of the case will contain \u003cb\u003en\u003c/b\u003e space separated integers \u003cb\u003ea\u003c/b\u003e\u003csub\u003e1\u003c/sub\u003e,...,\u003cb\u003ea\u003c/b\u003e\u003csub\u003e\u003cb\u003en\u003c/b\u003e\u003c/sub\u003e.\n\u003c/p\u003e\n\n\u003ch3\u003eOutput\u003c/h3\u003e\n\u003cp\u003eOutput a single number, the number of sequences, modulo 10\u003csup\u003e9\u003c/sup\u003e+7. \u003c/p\u003e\n\n\u003ch3\u003eConstraints\u003c/h3\u003e\n\u003cul\u003e\n\u003cli\u003e1 ≤ \u003cb\u003eT\u003c/b\u003e ≤ 100 \u003c/li\u003e\n\u003cli\u003e1 ≤ \u003cb\u003en\u003c/b\u003e ≤ 5\u003c/li\u003e\n\u003cli\u003e0 ≤ \u003cb\u003ea\u003c/b\u003e\u003csub\u003ei\u003c/sub\u003e \u003c 2\u003csup\u003e31\u003c/sup\u003e\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003ch3\u003eExample\u003c/h3\u003e\n\u003cpre\u003e\n\u003cb\u003eInput: \u003c/b\u003e\n4\n1\n42\n5\n5 4 3 2 1\n4\n1194533513 122420337 1448417648 120078455\n3\n31 2047 2147483647\n\n\u003cb\u003eOutput:\u003c/b\u003e\n147483634\n986095186\n0\n468598063\n\u003c/pre\u003e\n\n\u003ch3\u003eExplanation\u003c/h3\u003e\n\u003cp\u003e\nIn the first case, there are 2\u003csup\u003e31\u003c/sup\u003e possible sequences, so the answer is 2\u003csup\u003e31\u003c/sup\u003e modulo 10\u003csup\u003e9\u003c/sup\u003e+7 \u003d 147483634\n\u003c/p\u003e\n\n\u003cp\u003e\nFor the second case, one possible example of a valid sequence is b \u003d 9, 9, 18, 19, 32. We can check that this sequence is nondecreasing, and also, we have (\u003cb\u003ea\u003c/b\u003e\u003csub\u003e1\u003c/sub\u003e XOR b\u003csub\u003e1\u003c/sub\u003e) \u003d 12, (\u003cb\u003ea\u003c/b\u003e\u003csub\u003e2\u003c/sub\u003e XOR b\u003csub\u003e2\u003c/sub\u003e) \u003d 13, (\u003cb\u003ea\u003c/b\u003e\u003csub\u003e3\u003c/sub\u003e XOR b\u003csub\u003e3\u003c/sub\u003e) \u003d 17, (\u003cb\u003ea\u003c/b\u003e\u003csub\u003e4\u003c/sub\u003e XOR b\u003csub\u003e4\u003c/sub\u003e) \u003d 17, (\u003cb\u003ea\u003c/b\u003e\u003csub\u003e5\u003c/sub\u003e XOR b\u003csub\u003e5\u003c/sub\u003e) \u003d 33, which is also nondecreasing.\n\u003c/p\u003e\n\n\u003cp\u003e\nFor the third case, no sequences satisfy the conditions.\n\u003c/p\u003e"}}]}