{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\u003cscript\u003e window.katexOptions \u003d { disable: true }; \u003c/script\u003e\n\u003cscript type\u003d\"text/x-mathjax-config\"\u003e\n MathJax.Hub.Config({\n tex2jax: {\n inlineMath: [[\u0027$$$\u0027,\u0027$$$\u0027], [\u0027$\u0027,\u0027$\u0027]],\n displayMath: [[\u0027$$$$$$\u0027,\u0027$$$$$$\u0027], [\u0027$$\u0027,\u0027$$\u0027]]\n }\n });\n\u003c/script\u003e\n\u003cscript type\u003d\"text/javascript\" async src\u003d\"https://mathjax.codeforces.org/MathJax.js?config\u003dTeX-AMS_HTML-full\"\u003e\u003c/script\u003e","sections":[{"title":"","value":{"format":"HTML","content":"In a quaint village nestled in the mountains, there lived a creature named Marmot who had a peculiar diet of flowers. Marmot\u0027s dinners were not just about devouring flowers randomly; there was a unique rule to follow: Marmot would only eat white flowers if they appeared in groups of size k.\u003cbr\u003e\n\nMarmot ponders over the number of ways he can enjoy his meal. A meal can be represented as a sequence of several flowers, some of them white and some of them red. The task is to determine, for various scenarios, how many ways Marmot can consume between a and b flowers while adhering to his dining rule."}},{"title":"Input","value":{"format":"HTML","content":"The first line of the input consists of two integers t and k, denoting the number of test cases and the group size of white flowers, respectively.(1 ≤ t, k ≤ 10^5)\u003cbr\u003e\n\nFollowing that are t lines, each containing two integers ai and bi, representing the range of flowers for the respective test case.(1 ≤ ai ≤ bi ≤ 10^5)\n"}},{"title":"Output","value":{"format":"HTML","content":"For each test case, print the number of ways Marmot can enjoy his dinner within the given range of flowers, ensuring that white flowers appear only in groups of size k. Output each result modulo 1000000007 (10^9 + 7)."}},{"title":"Examples","value":{"format":"HTML","content":"3 2\u003cbr\u003e\n1 3\u003cbr\u003e\n2 3\u003cbr\u003e\n4 4\u003cbr\u003e\n"}},{"title":"Ans","value":{"format":"HTML","content":"6 \u003cbr\u003e\n5\u003cbr\u003e\n5\u003cbr\u003e"}}]}