Подсчитать число полупалиндромных чисел

Question

Я пробовал этот код, но каждый раз он выдает ошибку превышения лимита времени, так как я могу сократить время. Неотрицательное число называется «S semi-palindromi c», если оно делится на S и возможно переставить его цифры таким образом, чтобы полученное число было палиндроми c. Если исходное число имело D цифр (без начальных нулей), то учитывайте, что число, полученное в результате перестановки, должно иметь ровно D цифр (допускаются начальные нули).

Вычислить число "S semi-palindromi c "числа меньше 10 ^ K Входные данные В первой строке входных данных содержится одно целое число T, обозначающее количество тестовых случаев. Описание T-тестов приведено ниже. Первая и единственная строка каждого теста содержит два целых числа, разделенных пробелами S и K. Выходные данные Для каждого теста выведите одну строку, содержащую одно целое число - ответ по модулю 10 ^ 9 + 7.

Ограничения 1 ≤T≤20 1≤S≤16 1≤K≤10 ^ 18

Вот мой код

#include <iostream>
#include <math.h>
using namespace std;

int main() {
    int T=0;
    cin>>T;
    while(T>0)
    {
        int S=0,result=0;
        long double K=0, count = 1, n=0,k=1, a=pow(10,9) + 7;
        cin>>S>>K;
        n=S * k;
         while(n<pow(10,K))
             {    
              int arr[10]={0};
              long long int rem=0,num=0,flag=0;
                   num=n;
                   while(num>0)
                   {
                       rem=num%10;
                       num=num/10;
                       arr[rem]+=1;
                   }
                   for(int j=0;j<10;j++)
                   {
                       if(arr[j]%2 != 0)
                       {
                          flag++; 
                       }
                   }
                   if(flag <= 1)
                   {
                      count++; 
                   }
                   else
                    flag=0;
                   k++;
                   n=S * k;
            }
            result = count%a;
            cout<<result<<"\n";
        T--;
    }
    return 0;
}