{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003eOne day, Homer was bored in his house and decided to go in a journey to discover the lands of Springfield.The lands of Springfield is an infinite grid. Homer\u0027s house is located at cell (0, 0) and his journey consistedof N steps, where each step is either move one cell right or one cell down.\u0026nbsp;\u003c/p\u003e\n\u003cp\u003eBeing bored already, Homer didn\u0027t want his journey to be boring as well. He decided he won\u0027t move inthe same direction for more than K consecutive steps. Thus, a journey is considered to be interesting iffor each K+1 consecutive steps Homer has moved in both directions.\u0026nbsp;\u003cbr\u003e\u003c/p\u003e\n\u003cp\u003e\u003cimg alt\u003d\"QQ图片20200317150611.png\" src\u003d\"CDN_BASE_URL/1030387b1491bd5db00a3ed11e0505e3?v\u003d1666359471\" width\u003d\"450\" height\u003d\"201.82403433476395\"\u003e\u003c/p\u003e\n\u003cp\u003e\u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp; \u0026nbsp;Figure 1: Example with N\u003d5 and K\u003d2 (first test case).\u0026nbsp;\u003c/p\u003e\n\u003cp\u003eGiven N and K, count the number of interesting journeys Homer can make. Two Journeys are considered different if for some i the ith step in the first Journey differs from that of the second Journey. Since the number can be large, print it modulo 1,000,000,007.\u0026nbsp;\u003cbr\u003e\u003c/p\u003e\n\u003cp\u003e\u003cb\u003eInput\u0026nbsp;\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003e\u0026nbsp;Your program will be tested on one or more test cases. The first line of the input will be a single integer T, the number of test cases (1 ≤ T ≤ 500), followed by T test cases.Each test case will be presented on a single line containing two integers separated by a single space.The first integer will denote the number of steps in Homer\u0027s journey N, followed by the second integer K representing the maximum number of consecutive steps Homer can take while moving in the same direction, where (0 ≤ N ≤ 1e5) and (0 ≤ K ≤ 1e5).Output For each test case,\u003c/p\u003e\n\u003cp\u003e\u0026nbsp;\u003cb\u003eoutput\u0026nbsp;\u003c/b\u003e\u003c/p\u003e\n\u003cp\u003ea single line denoting the number of different journeys Homer can make modulo1,000,000,007.\u0026nbsp;\u003cbr\u003e\u003c/p\u003e"}},{"title":"Sample 1","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\u003e2\n5 2\n10 1\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e16\n2\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\u003cbr /\u003e"}}]}