{"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/LTIME19/mandarin/TASUMOBC.pdf\"\u003eMandarin Chinese \u003c/a\u003e and \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/LTIME19/russian/TASUMOBC.pdf\"\u003eRussian\u003c/a\u003e.\u003c/h3\u003e\r\n\r\n\r\n\u003cp\u003e As we all know, \u003ca href\u003d\"http://en.wikipedia.org/wiki/Binomial_coefficient\"\u003eBinomial Coefficient\u003c/a\u003e \u003cb\u003eC(n, r)\u003c/b\u003e is defined by the\r\nfollowing formula. \u003cbr\u003e\u003c/br\u003e\r\n\r\n\u003cimg src\u003d\"CDN_BASE_URL/2cd3a3e8a6926b0a4232b700fb292bcb?v\u003d1714226144\" \u003e\r\n\u003c/p\u003e\r\n\r\n\u003cp\u003e\r\nAlso define S(\u003cb\u003en\u003c/b\u003e) as follows. \u003cbr\u003e\u003c/br\u003e\r\n\r\n\u003cimg src\u003d\"CDN_BASE_URL/62aaf7e81e1b3ab00cde1c8ed37391d6?v\u003d1714226144\" \u003e \u003cbr\u003e\u003c/br\u003e\r\n\r\nNote that \u003cb\u003en\u003c/b\u003e will be provided to you as an input parameter.\u003c/li\u003e\r\n\r\nSince S(\u003cb\u003en\u003c/b\u003e) can be very large, please print it modulo \u003cb\u003e(10\u003csup\u003e9\u003c/sup\u003e + 7)\u003c/b\u003e.\r\n\u003c/p\u003e\r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\u003cul\u003e\r\n \u003cli\u003eThe first line contains a single integer \u003cb\u003eT\u003c/b\u003e representing the number of test cases.\u003c/li\u003e\r\n \u003cli\u003eEach of the next \u003cb\u003eT\u003c/b\u003e lines contains an integer \u003cb\u003en\u003c/b\u003e.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\u003cul\u003e\r\n \u003cli\u003eFor each test case, output a single line containing the value of \u003cb\u003eS(n) modulo (10\u003csup\u003e9\u003c/sup\u003e + 7)\u003c/b\u003e. \r\n\u003c/ul\u003e\r\n\r\n\u003ch3\u003eConstraints\u003c/h3\u003e\r\n\r\n\u003cp\u003e\r\n\u003cb\u003e10 points:\u003c/b\u003e\r\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eT\u003c/b\u003e ≤ \u003cb\u003e300\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003en\u003c/b\u003e ≤ \u003cb\u003e300\u003c/b\u003e\u003c/li\u003e\r\n\u003c/p\u003e\r\n\r\n\u003cp\u003e\r\n\u003cb\u003e30 points:\u003c/b\u003e\r\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eT\u003c/b\u003e ≤ \u003cb\u003e10\u003csup\u003e5\u003c/sub\u003e\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003en\u003c/b\u003e ≤ \u003cb\u003e5000\u003c/b\u003e\u003c/li\u003e\r\n\u003c/p\u003e\r\n\r\n\u003cp\u003e\r\n\u003cb\u003e60 points:\u003c/b\u003e\r\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003eT\u003c/b\u003e ≤ \u003cb\u003e10\u003csup\u003e5\u003c/sub\u003e\u003c/b\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cb\u003e1\u003c/b\u003e ≤ \u003cb\u003en\u003c/b\u003e ≤ \u003cb\u003e10\u003csup\u003e18\u003c/sub\u003e\u003c/b\u003e\u003c/li\u003e\r\n\u003c/p\u003e\r\n\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\r\n\u003cpre\u003e\u003cb\u003eInput:\u003c/b\u003e\r\n5\r\n1\r\n2\r\n3\r\n4\r\n5\r\n\r\n\u003cb\u003eOutput:\u003c/b\u003e\r\n2\r\n4\r\n2\r\n4\r\n8\r\n\r\n\u003c/pre\u003e\r\n"}}]}