{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003ch3\u003eRead problems statements in \u003ca target\u003d\"_blank\" \nhref\u003d\"https://www.codechef.com/download/translated/MARCH18/mandarin/CHEFKNN.pdf\"\u003eMandarin chinese\u003c/a\u003e, \u003ca target\u003d\"_blank\" \nhref\u003d\"https://www.codechef.com/download/translated/MARCH18/russian/CHEFKNN.pdf\"\u003eRussian\u003c/a\u003e and \u003ca target\u003d\"_blank\" \nhref\u003d\"https://www.codechef.com/download/translated/MARCH18/vietnamese/CHEFKNN.pdf\"\u003eVietnamese\u003c/a\u003e as well.\u003c/h3\u003e\n\n\u003cp\u003eChef has \u003cb\u003eK\u003c/b\u003e friends (numbered 1 through \u003cb\u003eK\u003c/b\u003e) and an array of length \u003cb\u003eN\u003c/b\u003e in which each element has a color; initially, each element has color 0. Chef agreed to let each of his friends (in the order from friend 1 to friend \u003cb\u003eK\u003c/b\u003e) perform the following operation:\n\u003cul\u003e\n\u003cli\u003echoose an arbitrary non-empty subarray\u003c/li\u003e\n\u003cli\u003epaint all elements in this subarray with color \u003cb\u003ei\u003c/b\u003e, where \u003cb\u003ei\u003c/b\u003e is the number of this friend\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/p\u003e\n\n\u003cp\u003eWhen an element is painted with some color, its original color is lost. This happens even if this element was already painted by some friend before.\u003c/p\u003e\n\n\u003cp\u003eChef is now wondering: how many distinct colorings of the final array are possible?\u003c/p\u003e\n\n\u003ch3\u003eInput\u003c/h3\u003e\n\u003cul\u003e\n\u003cli\u003eThe first line of the input contains a single integer \u003cb\u003eT\u003c/b\u003e denoting the number of test cases. The description of \u003cb\u003eT\u003c/b\u003e test cases follows.\u003c/li\u003e\n\u003cli\u003eThe first and only line of each test case contains two space-separated integers \u003cb\u003eN\u003c/b\u003e and \u003cb\u003eK\u003c/b\u003e.\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003ch3\u003eOutput\u003c/h3\u003e\n\u003cp\u003eFor each test case, print a single line containing one integer — the number of possible final arrays \u003cb\u003emodulo 163577857\u003c/b\u003e.\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\u003eK\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e ≤ 10\u003csup\u003e6\u003c/sup\u003e\u003c/li\u003e\n\u003cli\u003e1 ≤ sum of \u003cb\u003eN\u003c/b\u003e over all test cases ≤ 5 · 10\u003csup\u003e6\u003c/sup\u003e\u003c/b\u003e \n\u003c/ul\u003e\n\n\u003ch3\u003eSubtasks\u003c/h3\u003e\n\u003cp\u003e\u003cb\u003eSubtask #1 (10 points):\u003c/b\u003e 1 ≤ sum of \u003cb\u003eN\u003c/b\u003e over all test cases ≤ 500\u003c/p\u003e\n\n\u003cp\u003e\u003cb\u003eSubtask #2 (20 points):\u003c/b\u003e\n\u003cul\u003e\n\u003cli\u003e1 ≤ \u003cb\u003eN\u003c/b\u003e ≤ 2500\u003c/li\u003e\n\u003cli\u003e1 ≤ sum of \u003cb\u003eN\u003c/b\u003e over all test cases ≤ 10\u003csup\u003e4\u003c/sup\u003e\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/p\u003e\n\n\u003cp\u003e\u003cb\u003eSubtask #3 (30 points):\u003c/b\u003e\n\u003cul\u003e\n\u003cli\u003e1 ≤ \u003cb\u003eN\u003c/b\u003e ≤ 10\u003csup\u003e5\u003c/sup\u003e\u003c/li\u003e\n\u003cli\u003e1 ≤ sum of \u003cb\u003eN\u003c/b\u003e over all test cases ≤ 5 · 10\u003csup\u003e5\u003c/sup\u003e\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/p\u003e\n\n\u003cp\u003e\u003cb\u003eSubtask #4 (40 points):\u003c/b\u003e original constraints\u003c/p\u003e"}},{"title":"Sample 1","value":{"format":"MD","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\u003e3\n2 1\n2 2\n3 1\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e3\n5\n6\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cp\u003e\u003cb\u003eExample case 1:\u003c/b\u003e the final array can be [0, 1], [1, 0] or [1, 1].\u003c/p\u003e\n\u003cp\u003e\u003cb\u003eExample case 2:\u003c/b\u003e the final array can be [0, 2], [1, 2], [2, 0], [2, 1] or [2, 2].\u003c/p\u003e\n\u003cp\u003e\u003cb\u003eExample case 3:\u003c/b\u003e the final array can be [0, 0, 1], [0, 1, 0], [0, 1, 1], [1, 0, 0], [1, 1, 0] or [1, 1, 1].\u003c/p\u003e"}}]}