RT,我认为我的代码是$O(Wlog |W|)$的，但是为什么会T呢

#include<iostream>
#include<cstdio>
#include<vector>
#define pb push_back
#include<cstring>
using namespace std;
namespace INPUT{
    char buf[1<<20],*p1,*p2;
    #define gc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<20,stdin),p1==p2)?EOF:*p1++)
}
using namespace INPUT;
template<typename T>
inline T read(){
    T x=0,p=1;
    char ch=gc();
    for(;ch<'0'||ch>'9';ch=gc())
        if(ch=='-') p=-1;
    for(;ch>='0'&&ch<='9';ch=gc())
        x=(x<<3)+(x<<1)+(ch^48);
    return x*p;
}
#define ll long long
const ll mod=1e9+7;
ll qpow(ll x,ll k,ll mod=1e9+7){
	ll res=1;
	while(k){
		if(k&1) res=res*x%mod;
		x=x*x%mod,k>>=1;
	}
	return res;
}
const int M=3;
struct Matrix{
	ll c[M][M];
	Matrix() {memset(c,0,sizeof(c));}
	ll* operator[](int index){
		return c[index];
	}
	friend Matrix operator*(Matrix& A,Matrix& B){
		Matrix C;
		for(int i=1;i<=2;i++) for(int j=1;j<=2;j++)
			for(int k=1;k<=2;k++) C[i][j]=(C[i][j]+A[i][k]*B[k][j]%mod)%mod;
		return C;
	}
};
ll Fib(ll k){k--;
	Matrix base;
	base[1][1]=0;
	base[1][2]=base[2][1]=base[2][2]=1;
	Matrix res;
	res[1][1]=res[2][2]=1;
	res[1][2]=res[2][1]=0;
	while(k){
		if(k&1) res=res*base;
		base=base*base,k>>=1;
	}
	return res[2][2];
}
const int N=1e6+5;
vector<int>primes;
bool flag[N];
int mu[N];
int c[N];
ll Sum_Fib[N],Sum_c[N];
int n,k;
void init(int _n){
	mu[1]=1;
	for(int i=2;i<=_n;i++){
		if(!flag[i]) primes.pb(i),mu[i]=-1;
		for(auto prime:primes){
			if(i*prime>_n) break;
			flag[i*prime]=true;
			if(i%prime==0) break;
			mu[i*prime]=-mu[i];
		}
	}
	for(int i=1;i<=_n;i++){
		ll A=Fib(qpow(i,k,2000000016));
		for(int j=1;i*j<=_n;j++)
			Sum_Fib[i*j]=(Sum_Fib[i*j]+A*mu[j]%mod)%mod;
	}
	for(int T=1;T<=_n;T++) for(int i=1;i*T<=_n;i++)
		Sum_c[T]=(Sum_c[T]+c[i*T])%mod;
}
const int W=1e6;
int main(){
	// freopen("SP31893.in","r",stdin);
	// freopen("SP31893.out","w",stdout);
	n=read<int>(),k=read<int>();
	ll ans=0;
	for(int i=1;i<=n;i++) {
		int x=read<int>();
		c[x]++;
		ans=(ans-Fib(qpow(x,k,2000000016)))%mod;
	}
	init(W);
	for(int i=1;i<=W;i++){
		ans=(ans+Sum_Fib[i]*Sum_c[i]%mod*Sum_c[i]%mod)%mod;
	}
	cout<<ans*qpow(2,mod-2)%mod<<endl;
}