# Codeforces 1778D Flexible String Revisit
## 給兩個長度n之字串a和b，且其都由0或1組成，定義操作為隨機挑a中一個字元，如果為1則將其變0，為0則將其變1，問操作幾步使a變為b之期望操作步數(變為b後停止操作)，$n \le 10^6$。
> https://codeforces.com/contest/1778/problem/D

定義dp(i)為起始狀態a與b之字元相等個數有i個，期望操作幾步使得a等於b，然後我們很容易得到：
\begin{array}{ll}
& dp(i) = 1 + \frac{i}{n}dp(i-1) + \frac{n-i}{n}dp(i+1) \\
& dp(n) = 0 \\
& dp(0) = 1 + dp(1)
\end{array}
然後然後我就不會了==，感謝這位大老的想法又讓可憐菜雞學到一招遞推化簡技巧QQ
>https://codeforces.com/blog/entry/111780?#comment-999204
>
觀察上面第三式發現dp第0項只與dp第一項有關，考慮dp(1):

\begin{array}{ll}
& dp(1) = 1 + \frac{1}{n}dp(0) + \frac{n-1}{n}dp(2)
\end{array}

可以發現上式中dp(0)可直接拆成dp(1)與常數再化簡，則式子變為:
\begin{array}{ll}
& dp(1) = \alpha + \beta dp(2)
\end{array}

照這邏輯則dp(i)僅會跟dp(i+1)和兩個常數f(i),g(i)有關，可以得到:
\begin{array}{ll}
& dp(i) = f(i) + g(i) dp(i+1)
\end{array}
將最一開始之遞迴式之dp(i-1)代換掉比較係數可得:
\begin{array}{ll}
f(i) = \frac{n + if(i-1)}{n - ig(i-1)},\
g(i) = \frac{n - i}{n - ig(i-1)}
\end{array}
然後 就沒有然後了==

#include <bits/stdc++.h>
#pragma GCC optimize(3)
#define ll long long
#define pii pair<int, int>
#define pll pair<long long, long long>
#define F first
#define S second
#define endl '\n'
using namespace std;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;


ll qmul(ll x, ll y){
    ll cur = x, ans = 1;
    while(y > 0){
        if(y & 1) ans = (ans * cur) % mod;
        cur = (cur * cur) % mod;
        y >>= 1;
    }
    return ans;
}


void solve(){
    int n; cin >> n;
    string a, b; cin >> a >> b;
    int cnt = 0;
    for(int i=0; i<n; i++) if(a[i] == b[i]) cnt++;

    ll f[n+1], g[n+1], dp[n+1];
    f[0] = g[0] = 1;
    for(int i=1; i<=n-1; i++){
        ll inv = (n - g[i-1] * i % mod) % mod;
        if(inv < 0) inv += mod;
        inv = qmul(inv, mod - 2);
        f[i] = (n + f[i-1] * i) % mod * inv % mod;
        g[i] = (n - i) * inv % mod;
    }

    dp[n] = 0;
    for(int i=n-1; i>=cnt; i--){
        dp[i] = f[i] + g[i] * dp[i+1];
        dp[i] %= mod;
    }

    cout << dp[cnt] << endl;

} 


int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    
    int t =1;
    cin >> t;
    while(t--)
    solve();
    return 0;
}

###### tags: `dp` `probabilities` `math`