/**
 * @author      : cromarmot (yexiaorain@gmail.com)
 * @file        : D
 * @created     : 星期五 5月 13, 2022 20:35:36 CST
 */

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (int i=a;i<n;i++)

// 竞赛图 任意不同两点间都有恰好一条单向边
int n,m; // n 1e5, m 2e5
vector<int>p2[100010];

// scc -> 成链?

class Tarjan{
  vector<int> low;
  vector<int> dfn;
  stack<int> stk;
  vector<int> res;
  int n;
  int id = 0;
  void scc(int v) {
    low[v] = dfn[v] = ++id;
    stk.push(v);
    for(auto w:p2[v]){
      if(!dfn[w]){ // 未访问过
        scc(w);
        low[v] = min(low[v],low[w]);
      } else if(!res[w]){ // 访问过但没有结果(在栈中)
        low[v] = min(low[v],dfn[w]);
      }
    }
    int u;
    if(low[v] == dfn[v])  {
      do{
        res[u = stk.top()] = v;
        stk.pop();
      }while(u != v);
    }
  }
public:
  Tarjan(int SZ):n(SZ){
    low = vector<int>(n+1,0);
    dfn = vector<int>(n+1,0);
    stk = {};
    res = vector<int> (n+1,0);
  }
  vector<int> calc(){
    rep(i,1,n+1){
      if(!res[i]){
        scc(i);
      }
    }
    return res;
  }
};

vector<int> p3[100010];
int du[100010];

void work(){
  scanf("%d %d",&n,&m);
  Tarjan tarjan(n);
  rep(i,1,n+1){
    p2[i] = {};
    p3[i] = {};
    du[i] = 0;
  }
  rep(i,0,m){
    int u,v;
    scanf("%d %d",&u,&v);
    p2[u].push_back(v);
  }
  // a->b / b->a 至少满足一条
  // scc 成链? 唯一拓扑顺序
  vector<int> num = tarjan.calc(); // scc 联通分量 标识
  vector<int> sccsz(n+1,0);
  rep(i,1,n+1){
    sccsz[num[i]]   ++;
  }
  rep(i,1,n+1){
    if(sccsz[i] == 2){
      // 竞赛图不能创造大小为2的scc!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
      printf("NO\n");
      return ;
    }
  }

  // rep(i,1,n+1){
  //   printf("scc: %lld: %d\n",i,num[i]);
  // }
  // 转化为联通分量关系
  rep(i,1,n+1){
    for(auto item:p2[i]){
      if(num[i] == num[item])continue;
      p3[num[i]].push_back(num[item]);
    }
  }
  rep(i,1,n+1){
    if(num[i] != i)continue;
    sort(p3[i].begin(),p3[i].end());
    int itr = 0;
    rep(j,0,(int)p3[i].size()){
      if(j==0 || p3[i][j] != p3[i][j-1]){ // 去重
        p3[i][itr++] = p3[i][j];
        // i -> p3[i][j]
        du[p3[i][j]]++; // 入度
      }
    }
    p3[i].resize(itr);
  }
  // 拓扑 联通分量中 唯一顺序
  // 入度为0
  vector<int> d0;
  rep(i,1,n+1){
    if(num[i] != i)continue;
    if(du[i] == 0)d0.push_back(i);
  }
  while(d0.size()) { // == 1
    if(d0.size() > 1){
      printf("NO\n");
      return ;
    }
    int i = d0[0];
    // printf("D0:%d\n",i);
    d0.pop_back();
    rep(j,0,(int)p3[i].size()){
      // i -> p3[i][j]
      du[p3[i][j]]--;
      if(du[p3[i][j]] == 0){
        d0.push_back(p3[i][j]);
        if(d0.size() > 1){
            printf("NO\n");
            return ;
        }
      }
    }
  }
  printf("YES\n");
}


int main(){
  int t;
  scanf("%d",&t);
  while(t--){
    work();
  }
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define MOD 1000000007
#define rep(i,a,n) for (ll i=a;i<n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)
#define pb push_back
const double pi = acos(-1.0);

int n;
int a[1000010];

int main(){
  ll ans = 1;
  cin>>n;
  rep(i,1,n+1){
    scanf("%d",a+i);
    if(i-a[i]+1 <= 0){
      ans = 0;
    }else{
      (ans*=i-a[i]+1)%=MOD;
    }
  }
  printf("%lld\n",ans);
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)

const int N = 262144;

vector<int> lr(N*4+10,-1); // -1 unset 0:01, 1:10

int a[N+10];

int n;
bool build(int pos,int val,int idx = 1,int pwr = 0){
  if(pwr == n)return true;
  int direction = pos%2;
  int v = direction != val%2;
  if(lr[idx] != -1 && lr[idx] != v){
    return false;
  }
  lr[idx] = v;
  return build(pos/2,val/2,idx*2+direction,pwr+1);
}

int xorcache[20] = {0}; // 不要实际的xor, 修改代价大

vector<int>ans;

void fix(int val){
  // printf("Fix %d\n",val);
  int x = 0;
  {
    int pwr = n-1;
    int v = val;
    while(pwr--){
      if(v%2 == (lr[v/2] ^ xorcache[pwr])){
        x |= (1<<(pwr));
      }
      v/=2;
    }
  }
  // printf("xor %d\n",x);
  if(x){
    ans.push_back(x);
    rep(pwr,0,n){
      if((1<<pwr) & x)xorcache[pwr]^=1; // 标记
    }
  }
  // printf("+1\n");
  {
    int idx = 1;
    rep(pwr,0,n){
      if(lr[idx]^xorcache[pwr]){
        idx=idx*2;
      }else{
        idx=idx*2+1;
      }
      lr[idx/2] ^= 1;
    }
  }
  ans.push_back(-1);
}


int main(){
  cin>>n;
  rep(i,0,(1<<n)){
    scanf("%d",a+i);
  }
  rep(i,0,(1<<n)){
    int r = build(i,a[i]);
    if(!r){
      printf("No\n");
      return 0;
    }
  }
  // rep(i,1,8){
  //   printf("lr[%lld]= %d\n",i,lr[i]);
  // }
  rep(i,(1<<(n-1)),(1<<n)){
    if(lr[i] == 0)continue;
    fix(i);
  }
  int x = 0;
  rep(pwr,0,n){
    if(lr[1<<pwr] ^ xorcache[pwr]){
      x |= 1<<pwr;
      xorcache[pwr] ^= 1;
    }
  }
  if(x){
    ans.push_back(x);
  }
  rep(pwr,0,n){
    rep(i,(1<<pwr),(1<<(pwr+1))){
      if(lr[i]^xorcache[pwr]){
        printf("No\n");
        return 0;
      }
    }
  }
  printf("Yes\n");
  printf("%d\n",(int)ans.size());
  rep(i,0,(int)ans.size()){
    printf("%d ",ans[i]);
  }
  printf("\n");
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define MOD 998244353
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define per(i,a,n) for (ll i=n;i-->(ll)a;)

int n,k;
int v[1000010];

int main(){
  int t;
  cin>>t;
  while(t--){
    scanf("%d %d",&n,&k);
    rep(i,0,n){
      scanf("%d",v+i);
    }
    ll ans = 1;
    rep(i,0,n){
      if(i < k){ // 前k个自由
        (ans*=i+1)%=MOD;
      }else if(v[i-k] == -1){ // -1 自由
        (ans*=i+1)%=MOD;
      }else if(v[i-k] == 0){ // <=k 即 [0..k] , k+1种
        (ans*=k+1)%=MOD;
      } // v[i-k] != 0 , 唯一选择(从后向前)
    }
    // 最后k个一定是0(也可以-1表示0)
    rep(i,0,k){
      if(v[n-1-i] > 0)ans = 0;
    }
    printf("%lld\n",ans);
  }
  return 0;
}

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
const int N=2e5;
#define SEG_ROOT 1,1,n
#define SEG_L (o<<1)
#define SEG_R (o<<1|1)
#define mid (l+r)/2
#define SEG_L_CHILD SEG_L,l,mid
#define SEG_R_CHILD SEG_R,mid+1,r
#define SEG_L_CHILD_Q SEG_L,l,mid,ql,qr
#define SEG_R_CHILD_Q SEG_R,mid+1,r,ql,qr
int n; // 数组长度
int a[N+10]; // 原始排列 1-index
int a2i[N+10]; // 值到下标 a2i[value] = index
int di; // 单调栈的尾部下标
int d[N+10]; // 单调栈,存的原数组的下标 1-index, d[stack-index] = a-index
int i2di[N+10]; // [a中下标] = 栈中下标 映射  i2di[a-index] = stack-index , 0(表示不在栈中)
int ti; // 当前遍历的个数 = i-1 or i
int p[N+10]; // p[stack-index] = 左侧最大合法a-index
ll ans[1000005]; // 询问的答案数组
vector<pair<int,int> >q[1000005]; // 询问 q[right] = vector<pair<left,query index> >
vector<int> w[N + 10]; // 因数分解 w[value]= vector<value的因数>
struct seg {
  // 答案 = x * ti + y
  ll x; // 合法的左端点位置数
  ll y; // (真实答案 与 x*ti 之间补充的差), 辅助变量, 因为直接记录答案无法维护x, 同理也可以记录(真实答案,x), y = 该段贡献 - x*ti, (x0,y0)=>(x1,y1) : (y0+x0*ti) + x1 = (y1+x1*(ti+1)), y1 = y0 - (x1-x0)*ti
  ll tg; // 未向下传递的ti的和, y += (+/- ti) * len
  ll len; // 对应区间长度 简化书写
} tr[N*4 + 10];
// 初始化 线段树, 只有设置len = 区间长度,其它x,y,tg全为0
void make(int o,int l,int r){
  tr[o].len=r-l+1;
  if (l==r) return;
  make(SEG_L_CHILD);
  make(SEG_R_CHILD);
}
// lazy tag 下降
void down(int o) {
  // x
  if (tr[o].x == tr[o].len) {
    tr[SEG_L].x = tr[SEG_L].len;
    tr[SEG_R].x = tr[SEG_R].len;
  }
  if (tr[o].x==0) {
    tr[SEG_L].x=0;
    tr[SEG_R].x=0;
  }
  // 能向下的tag一定是区间全覆盖的
  if(tr[o].tg != 0){
    assert(tr[o].x == tr[o].len || tr[o].x == 0);
    // y, 如下clear和add 同样的 y += tg * len
    tr[SEG_L].y+=tr[o].tg*tr[SEG_L].len;
    tr[SEG_R].y+=tr[o].tg*tr[SEG_R].len;
    // tg
    tr[SEG_L].tg+=tr[o].tg;
    tr[SEG_R].tg+=tr[o].tg;
    tr[o].tg=0;
  }
}
// 更新 o
void up(int o) {
  tr[o].x=tr[SEG_L].x+tr[SEG_R].x; // 贡献数
  tr[o].y=tr[SEG_L].y+tr[SEG_R].y; // 修正值
}
// 保证 tr[o].x == tr[o].len
void clear(int o,int l,int r,int ql,int qr) {
  if (ql <= l && r <= qr) {
    // 贡献变化 tr[o].x * ti + tr[o].y => 0 * ti (当前轮) + (tr[o].y + ti * tr[o].len)
    // (tr[o].y + ti * tr[o].len) - (tr[o].x * ti + tr[o].y)
    // = ti * (tr[o].len - tr[o].x)
    // = 0
    assert(tr[o].x == tr[o].len);
    tr[o].tg+=ti; // 选中 -> 未选 未向下传递的, 对于下一级来说,也是 y+=ti*(len-x), 所以+ti传下去
    tr[o].y += ti*tr[o].len;// y += ti * x => y += ti * len
    tr[o].x=0;
    return;
  }
  down(o);
  if (ql<=mid) clear(SEG_L_CHILD_Q);
  if (qr>mid) clear(SEG_R_CHILD_Q);
  up(o);
}
// [ql..qr] 现在合法
// 保证了 tr[o].x == 0
void add(int o,int l,int r,int ql,int qr) {
  if (ql <= l && r <= qr) {
    // 贡献变化 tr[o].x * ti + tr[o].y => tr[o].len * (ti+1) 下一轮 + (tr[o].y - ti * tr[o].len)
    // (tr[o].len * (ti+1) + tr[o].y - ti * tr[o].len) - (tr[o].x * ti + tr[o].y)
    // = tr[o].len - (tr[o].x * ti)
    // = tr[o].len
    assert(tr[o].x == 0);
    tr[o].tg += -ti; // 未选 -> 选中 未向下传递的
    tr[o].y += -ti*tr[o].len; // y += -ti*(len - x) => y+= -ti * len
    tr[o].x=tr[o].len;
    return;
  }
  down(o);
  if (ql<=mid) add(SEG_L_CHILD_Q);
  if (qr>mid) add(SEG_R_CHILD_Q);
  up(o);
}
ll find(int o,int l,int r,int ql,int qr) {
  if (ql <= l && r <= qr) return tr[o].y+ti*tr[o].x; // 如segtree的设计定义
  down(o);
  ll ret = 0;
  if (ql<=mid) ret+=find(SEG_L_CHILD_Q);
  if (qr>mid) ret+=find(SEG_R_CHILD_Q);
  return ret;
}
int main() {
  int m; // 询问次数
  scanf("%d%d",&n,&m);
  // 读入排列
  rep(i,1,n+1){
    scanf("%d",&a[i]);
    a2i[a[i]]=i;
  }
  // 读入询问
  rep(i,1,m+1) {
    int l,r;
    scanf("%d%d",&l,&r);
    q[r].emplace_back(l,i);
  }
  // 因数
  rep(i,1,n+1)
    for (int j=i;j<=n;j+=i)
      w[j].emplace_back(i);
  // 初始化 线段树, 只有设置len = 区间长度,其它x,y,tg全为0
  make(SEG_ROOT);
  rep(i,1,n+1) { // a[i]
    while (di && a[d[di]]<a[i]) { // 新加入的值, 比单调栈中的最小的小, 移除操作
      if (p[di]>d[di-1]) clear(SEG_ROOT,d[di-1]+1,p[di]); // 从贡献标记为不贡献, 但是对于总的贡献不变
      // 出栈
      i2di[d[di]]=0;
      di--;
    }
    for (int j=a[i];j<=n;j+=a[i]) { // j = a[i] 的倍数, j 作为最大值时
      int k=i2di[a2i[j]]; // j在栈中下标
      if (!k) continue; // 不在栈中
      int l=d[k-1]+1,r=d[k]; // 左端点在范围 a[l..r] 中
      int e=a2i[j/a[i]]; // 乘起来等于j的另一个因数在a中的下标
      if (e<l || e>=i) continue; // e 在范围 a[l..i) 中, 不能选同一个ie平方
      e=min(e,r); // 左端点范围的最大值 a[l..e]
      if (e<=p[k]) continue; // p[k] 最大值不更新
      // a[l..p[k]] 合法 => a[l..e] 合法
      add(SEG_ROOT,p[k]+1,e); // 把[p[k]+1,e] 从不贡献变成贡献, 更新到本轮结束时该有的(x,y)
      p[k]=e;
    }
    // 入栈
    d[++di]=i;
    i2di[i]=di;
    p[di]=d[di-1]; // 初始化p[di]表示以a[i]作为峰, 左侧端点不贡献
    for (auto j:w[a[i]]) { // 枚举 因子对 (j,a[i]/j)
      int l=d[di-1]+1;
      // int r=i;
      int e1=a2i[j];
      int e2=a2i[a[i]/j];
      if (e2<=e1) continue; // 减少重复计算,主要是不等于
      if (e1<l || e2>i) continue; // [l-1..e1..e2..i+1]
      if (e1<=p[di]) continue; // 不会更新可行值 [p[di] .. e1 .. i]
      add(SEG_ROOT,p[di]+1,e1); // 从不贡献记为贡献, 更新到本轮结束时该有的(x,y)
      p[di]=e1; // 更新
    }
    ti++;
    for (auto t:q[i]) ans[t.second] = find(SEG_ROOT,t.first,i); // 查询[l = t.first,r = i]
  }
  rep(i,1,m+1) printf("%lld\n",ans[i]);
  return 0;
}

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define MOD 998244353
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)

ll a[2010];
ll pro[2010][2010]; // [v][cnt] 结果 <= v 的有cnt个的概率
ll c[2010][2010];

ll mypow(ll v,ll pwr){
  v=(v+MOD)%MOD;
  ll r = 1;
  while(pwr){
    if(pwr%2)(r*=v)%=MOD;
    (v*=v)%=MOD;
    pwr/=2;
  }
  return r;
}

// C(m,n) = m!/(n!(m-n)!)
ll C(ll m,ll n){
  if(n > m)return 0;
  return c[m][n];
}

int main(){
  rep(i,1,2005){
    c[i][0] = c[i][i] = 1;
    rep(j,1,i){
      c[i][j] = (c[i-1][j-1] + c[i-1][j])%MOD;
    }
  }

  ll n,m,k,x;
  cin>>n>>m>>k>>x;
  ll invm = mypow(m,MOD-2);
  x--; // 先减1
  rep(i,0,n){
    scanf("%lld",a+i);
  }
  sort(a,a+n);
  rep(v,1,m+1){
    int stx = 0;
    rep(i,0,n){
      if(a[i] <= v)stx++;
      else break;
    }
    if(stx == x){ // 结果必定 x
      pro[v][x] = 1;
      continue;
    }
    // p = v/m
    ll p = v * invm %MOD;
    rep(endx,0,n+1){
      if(stx < x){ // stx <= endx <= x
        if(stx <= endx && endx < x){
          // C(k,endx-stx) * p^(endx-stx) * (1-p)^(k-(endx-stx))
          pro[v][endx] = C(k,endx-stx) * mypow(p,endx-stx) %MOD * mypow(1-p,k-(endx-stx)) % MOD;
        }
      }else { // stx > x => stx >= endx >= x
        if(stx >= endx && endx > x){
          // C(k,stx-endx) * (1-p)^(stx-endx) * p^(k-(stx-endx))
          pro[v][endx] = C(k,stx-endx) * mypow(1-p,stx-endx) %MOD * mypow(p,k-(stx-endx)) % MOD;
        }
      }
    }
    // 最后处理 (endx == x) , 等于 1-其它概率和
    pro[v][x] = 1;
    rep(endx,0,n+1){
      if(endx == x)continue;
      (pro[v][x] -= pro[v][endx])%=MOD;
    }
  }
  ll leqv[2010] = {0};
  ll ans = 0;
  rep(v,1,m+1){
    rep(cnt,0,n+1){
      (leqv[v] += cnt*pro[v][cnt]%MOD)%=MOD; // 期望长度 = sum{期望*长度}
    }
    (ans += v*(leqv[v] - leqv[v-1]) %MOD)%=MOD; // count( == v) = count(<= v) - count(<= v-1)
  }
  printf("%lld\n", ((ans * mypow(m,k)%MOD)+MOD)%MOD); // 频次 = 总次数 * 频率
  return 0;
}