#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

using namespace std;

#define ll long long

#define N 100

#define P 1000000007

char getc(){char c=getchar();while ((c<'A'||c>'Z')&&(c<'a'||c>'z')&&(c<''||c>'')) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

ll n,m;

int T,k,ans,f[N][][][],a[N],b[N];

void inc(int &x,int y){x+=y;if (x>=P) x-=P;}

int calc(ll n,ll m)

{

    int t=-;

    while (n) a[++t]=n%k,n/=k;

    for (int i=;i<=t;i++) b[i]=m%k,m/=k;

    memset(f,,sizeof(f));

    f[t+][][][]=;

    for (int i=t;~i;i--)

        for (int j=;j<=;j++)

            for (int x=;x<=;x++)

                for (int y=;y<=;y++)

                    for (int p=x;p<=;p++)

                        for (int q=y;q<=;q++)

                        {

                            int ln=x==?a[i]:,rn=x==?a[i]:(p==?a[i]-:k-),lm=y==?b[i]:,rm=y==?b[i]:(q==?b[i]-:k-);

                            int s=;

                            for (int u=ln;u<=rn;u++)

                                for (int v=lm;v<=rm;v++)

                                if (v<=u) s++;

                            inc(f[i][j][x][y],1ll*f[i+][j][p][q]*s%P);

                            if (j) inc(f[i][j][x][y],1ll*f[i+][j-][p][q]*((rn-ln+)*(rm-lm+)-s)%P),

                            inc(f[i][j][x][y],1ll*f[i+][j][p][q]*((rn-ln+)*(rm-lm+)-s)%P);

                        }

    return ((f[][][][]+f[][][][])%P+(f[][][][]+f[][][][])%P)%P;

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj4737.in","r",stdin);

    freopen("bzoj4737.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    T=read(),k=read();

    while (T--)

    {

        cin>>n>>m;m=min(n,m);

        if (m&) ans=(P-(m%P)*((m+>>)%P)%P)%P;

        else ans=(P-((m+)%P)*((m>>)%P)%P)%P;

        inc(ans,calc(n,m));

        cout<<ans<<endl;

    }

    return ;

}