不要用费马小定理，过不了。

正解是通分+预处理（幂和乘积）。

不要告诉我你看了这个都没有思路 $\dots$

  for(int i=1; i<=n; i++){
  		read(a[i]);
  		kk[i] = (1ll*kk[i-1]*k)%p;
  		sum1[i] = (1ll*sum1[i-1]*a[i])%p;
  	}
  	sum2[n+1] = 1;
  	for(int i=n; i>=1; i--){
  		sum2[i] = (1ll*sum2[i+1]*a[i])%p;
  	}

同机房的蒟蒻不要再问我怎么做了！！！