C++ :

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
using namespace std;
char s[100005];
int p;
const long long mod=(long long)(1000000007);
int change(char c)
{
    if(c>='0'&&c<='9')
        return c-'0';
    return c-'A'+10;
}

int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        cin>>s>>p;
        int len=strlen(s);
        long long tmp=0;
        long long res=0;
        for(int i=len-1;i>=0;i--)
        {
            res+=change(s[i])*tmp;
            res%=mod;
            tmp=tmp*p+1;
            tmp%=mod;
        }
        cout<<res<<endl;
    }
}