Problem: <image>

To monitor cryptocurrency exchange rates trader William invented a wonderful device consisting of n lights arranged in a row. The device functions in the following way:

Initially, all lights on William's device are turned off. At the beginning of a new iteration the device randomly, with a uniform distribution, picks a light that is turned off and turns it on, telling William which cryptocurrency he should invest in. After this iteration if any k consecutive lights contain more than one turned on light, then the device finishes working.

William doesn't like uncertainty, so he wants you to calculate the expected value of the number of lights that are turned on in the device after it finishes working.

Input

Each test contains multiple test cases. The first line contains the number of test cases t (1 ≤ t ≤ 10). Description of the test cases follows.

The only line for each test case contains two integers n and k (2 ≤ k ≤ n ≤ 10^5), which are the total number of lights and the length of subsegment of lights that are being checked, respectively.

Output

For each test case print the answer, modulo 10^9+7. 

Formally, let M = 10^9+7. It can be shown that the answer can be expressed as an irreducible fraction p/q, where p and q are integers and q not ≡ 0 \pmod{M}. Output the integer equal to p ⋅ q^{-1} mod M. In other words, output such an integer x that 0 ≤ x < M and x ⋅ q ≡ p \pmod{M}.

Example

Input


3
3 2
15 2
40 15


Output


333333338
141946947
329622137

Note

Explanation of the first sample test case:

Let's write out all possible sequences of light toggles, which will make the device complete its operation:

  1. (1, 2) — 2 lights are turned on 
  2. (1, 3, 2) — 3 lights are turned on 
  3. (2, 1) — 2 lights are turned on 
  4. (2, 3) — 2 lights are turned on 
  5. (3, 2) — 2 lights are turned on 
  6. (3, 1, 2) — 3 lights are turned on 



Then the final expected value will be equal to 2/6 + 3/6 + 2/6 + 2/6 + 2/6 + 3/6 = 14/6 = 7/3. 

Then the required output will be 333333338, since 333333338 ⋅ 3 ≡ 7 \pmod{10^9+7}.

Solution (in CPP):

Solution:
#include<bits/stdc++.h>
using namespace std;

//======================
//
// Template OleschY
//
// Die M�glichkeiten der deutschen Grammatik k�nnen
// einen, wenn man sich darauf, was man ruhig, wenn
// man m�chte, sollte, einl�sst, �berraschen.
// - @Gedankenbalsam
//
//======================

//======================
//      MODULE
//======================
struct ModInt;
vector<ModInt> inverse();

using ModType = long long; // set Type. Cann multiply ints if using long long.
struct ModInt
{
    static inline vector<ModInt> precalcInverse;
    static void precalc()
    {
        precalcInverse = inverse();
    }

    static inline ModType mod = 1e9 + 7; // Set this value
    ModType val;
    ModInt(ModType v = 0) : val(v % mod) { }
    static void setMod(ModType m)
    {
        mod = m;
        if(precalcInverse.size() > 0)
        {
            precalcInverse = inverse();
        }
    }
    ModInt operator-() const
    {
        return ModInt(val ? mod - val : val);
    }
    ModInt &operator+=(ModInt a)
    {
        if ((val += a.val) >= mod) val -= mod;
        return *this;
    }
    ModInt &operator-=(ModInt a)
    {
        if ((val -= a.val) < 0) val += mod;
        return *this;
    }
    ModInt &operator*=(ModInt a)
    {
        val = (val * a.val) % mod;
        return *this;
    }
    ModInt &operator/=(ModInt a)
    {
        if(precalcInverse.size() > a.val)
        {
            *this *= precalcInverse[a.val];
            return *this;
        }
        ModType u = 1, v = a.val, s = 0, t = mod;
        while (v)
        {
            ModType q = t / v;
            swap(s -= u * q, u);
            swap(t -= v * q, v);
        }
        a.val = (s < 0 ? s + mod : s);
        val /= t;
        return (*this) *= a;
    }
    ModInt inv() const
    {
        return ModInt(1) /= (*this);
    }
    bool operator<(ModInt x) const
    {
        return val < x.val;
    }
};
ostream &operator<<(ostream &os, ModInt a)
{
    os << a.val;
    return os;
}
ModInt operator+(ModInt a, ModInt b)
{
    return a += b;
}
ModInt operator-(ModInt a, ModInt b)
{
    return a -= b;
}
ModInt operator*(ModInt a, ModInt b)
{
    return a *= b;
}
ModInt operator/(ModInt a, ModInt b)
{
    return a /= b;
}
ModInt pow(ModInt a, ModType e)
{
    ModInt x(1);
    for (; e > 0; e /= 2)
    {
        if (e % 2 == 1) x *= a;
        a *= a;
    }
    return x;
}
// compute inv[1], inv[2], ..., inv[mod-1] in O(n) time
vector<ModInt> inverse()
{
    ModType mod = ModInt::mod;
    vector<ModInt> inv(mod);
    inv[1].val = 1;
    for (ModType a = 2; a < mod; ++a)
        inv[a] = inv[mod % a] * ModInt(mod - mod / a);
    return inv;
}
ModInt stringToModInt(string s)
{
    ModType val = 0;
    for (int i = 0; i < s.size(); ++i)
        val = (val * 10 + (s[i] - '0')) % ModInt::mod;
    return ModInt(val);
}

//======================
//      Combinatorics
//======================

using CombType = ModInt; // set Type
struct Combinatorics
{
    vector<CombType> factorial = {1};
    int nPrecalcFactorial = 0;

    void precalcFactorial(int n)
    {
        CombType sum = factorial[nPrecalcFactorial];
        for(long long i = nPrecalcFactorial + 1; i <= n; i++)
        {
            sum *= i;
            factorial.push_back(sum);
        }
        nPrecalcFactorial = max(nPrecalcFactorial ,n);
    }

    CombType binomial(int n, int k)
    {
        CombType res = 1;
        if(k<0 || k>n)
            return 0;
        if(nPrecalcFactorial < n)
        {
            for (int i = 0; i < k; i++)
            {
                res = res * (n - i) / (i + 1);
            }
        }
        else
        {
            res = factorial[n];
            res /= factorial[k];
            res /= factorial[n - k];
        }
        return res;
    }

};
/*{
    ModInt::setMod(7);
    //ModInt::precalc(); //Only for small mods!
    Combinatorics comb;
    comb.precalcFactorial(ModInt::mod);
}*/

//======================
// Solution Single testcase
//======================
int n, k;
Combinatorics comb;

int solve()
{
    cin >> n >> k;
    comb.precalcFactorial(n);
    ModInt ans=1;
    for(int p = 1; p <= n; ++p)
    {
        long long test=n-(p-1)*(k-1);
        if(p>test)
            break;
        ans+=comb.binomial(n-(p-1)*(k-1),p)/comb.binomial(n,p);
    }
    cout << ans << "\n";
	return 0;
}

//======================
// Technical stuff
//======================

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    comb.precalcFactorial(4);
    comb.precalcFactorial(4);
    comb.precalcFactorial(2);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    //freopen("a.out","w",stdout); // console output is better (in most cases)
#else
    // add i/o method of specific testing system
#endif
    int ntest=1;
    cin >> ntest;
    for(int test = 0; test < ntest; ++test)
    {
		solve();
    }
    return 0;
}