竟然没有详细讲平面图欧拉公式的，写一篇。

首先我们知道平面图欧拉公式在期望意义下也成立，也即 $E(|V|)+E(|F|)-E(|E|)-1=E(k)$。同时需要强调的是平面图欧拉公式的 $|F|$ 实际上是算上最外面的面的，所以说式子转化为 $E(k)=E(|V|)+E(|F|)-E(|E|)$。

首先直接按照原本的网格图计算是错误的，因为这里的“连通分量”指的不是原图的连通分量，而是其对偶图的连通分量。考虑对偶图。此时 $|V|=k$，$E(|V|)=k$。考虑计算 $E(|E|)$ 也即相邻个数的期望套路的拆成每对点成为相邻的概率之和。每一对点具有相同的形式，而一对点的答案显然为 $\dfrac{\binom{2n-2}{k-2}}{\binom{2n}{k}}=\dfrac{k(k-1)}{2n(2n-1)}$，然后乘以总对数 $3n-2$，为 $\dfrac{k(k-1)(3n-2)}{2n(2n-1)}$。考虑计算 $E(|F|)$ 其实就是一个 $2\times 2$ 方格都成立的个数也就是 $\dfrac{\binom{2n-4}{k-4}}{\binom{2n}{k}}=\dfrac{k(k-1)(k-2)(k-3)}{2n(2n-1)(2n-2)(2n-3)}$。乘以对数 $n-1$ 最终值为 $\dfrac{(n-1)k(k-1)(k-2)(k-3)}{2n(2n-1)(2n-2)(2n-3)}$。

直接按照公式计算即可。

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr ll mod = 998244353;
void prec(int subtask_id) {
  return;
}
ll qpow(ll x, ll y) {
  ll ans = 1;
  while(y) {
    if(y & 1) ans = ans * x % mod;
    x = x * x % mod;
    y >>= 1;
  }
  return ans;
}
int solve(int nn, int kk) {
  ll n = nn, k = kk;
  ll ans = n - 1, ans2 = 1;
  for(int i = 0; i < 4; ++i) (ans *= qpow((2 * n - i) % mod, mod - 2)) %= mod;
  for(int i = 0; i < 4; ++i) (ans *= k - i) %= mod;
  ans2 = k * (k - 1) % mod * ((3 * n - 2) % mod) % mod * qpow(2 * n % mod, mod - 2) % mod;
  (ans2 *= qpow((2 * n - 1) % mod, mod - 2)) %= mod;
  //cout << ans << " " << ans2 << endl;
  (ans += k) %= mod, (ans += mod - ans2) %= mod;
  return ans;
}
/*int main() {
  int c, t;
  ll n, k;
  cin >> c >> t;
  while(t--) {
    cin >> n >> k;
    cout << solve(n, k) << endl;
  }
  return 0;
}*/