给个字符串可以$b_i$的前后缀倒置并交换，如果相同表示本质一样。询问有多少本质不同的串。

差分一下发现可以组成$2^m$种变换的方法。

根据Burnside引理，等价类的个数等于所有置换不动点个数的平均值

$ans= \frac{1}{∣G∣}\sum_{g∈G} A_g$

比如$1,3,5$，其实就是$[0,1],[2.3],[4,5]$这三个的组合。

对于总长度为$len$的变换，应该是$A^{n-len}$,$len$部分对应的每一位不变。

答案就是$\frac{1}{2^m}\sum A^n(\frac{1}{A^{len_1}}+\frac{1}{A^{len_2}}…)$

括号直接套路生成函数$\prod (1+\frac{1}{A^{d_i}})$

代码

```c++

include

using namespace std;
typedef long long ll;

define pii pair

define mk make_pair

const int N = 1e6 + 10;
const int mod = 998244353;
namespace math
{
int inc(int x, int y) { return (x + y >= mod) ? (x + y - mod) : (x + y); }
int del(int x, int y) { return (x - y < 0) ? (x - y + mod) : (x - y); }
int gcd(int a, int b)
{
return b == 0 ? a : gcd(b, a % b);
}
int qpow(int a, int x, int mo)
{
int res = 1;
while (x)
{
if (x & 1)
res = 1ll res a % mod;
a = 1ll a a % mod;
x >>= 1;
}
return res;
}
int Fac[N], invFac[N];
void Finit(int n)
{
Fac[0] = 1;
invFac[0] = 1;
for (int i = 1; i <= n; i++)
Fac[i] = 1ll Fac[i - 1] i % mod;
invFac[n] = qpow(Fac[n], mod - 2, mod);
for (int i = n - 1; i >= 1; i—)
invFac[i] = 1ll invFac[i + 1] (i + 1) % mod;
}
int C(int n, int m)
{
if (m == 0)
return 1;
if (n < m || m < 0)
return 0;

    return (int)(1ll * Fac[n] * invFac[m] % mod * invFac[n - m] % mod);
}

} // namespace math

using namespace math;

int read()
{
int x = 0, f = 1;
char c = getchar();
while (c < ‘0’ || c > ‘9’)
{
if (c == ‘-‘)
f = -1;
c = getchar();
}
while (c >= ‘0’ && c <= ‘9’)
x = (x << 1) + (x << 3) + c - ‘0’, c = getchar();
return x * f;
}
int main()
{

int n = read(), m = read(), A = read();
int invA = qpow(A, mod - 2, mod);
int inv2 = qpow(2, mod - 2, mod);
int res = 1;
vector<int> a(m + 1);
for (int i = 1; i <= m; i++)
    a[i] = read();
for (int i = 1; i <= m; i++)
{
    res = 1ll * res * (1 + qpow(invA, a[i] - a[i - 1], mod)) % mod;
}

cout
    << 1ll * res * qpow(inv2, m, mod) % mod * qpow(A, n, mod) % mod << endl;

}