///////////
// // //
// ////////////////////
// // //
//
///////////
//
//
// // // //////// /\ /////////
// // // // // // //
// //////// // // // // //
// // // // // // //
////////// //////// // // // /////////////
#pragma GCC optimize(2)
#pragma G++ optimize(2)
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <map>
#include <set>
#include <queue>
#include <string>
#include <cstring>
#include <cmath>
#include <list>
#include <stack>
#include <array>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <random>
#include <numeric>
#include <functional>
//#include <Windows.h>
using namespace std;
#define fa(i,op,n) for (int i = op; i <= n; i++)
#define fb(j,op,n) for (int j = op; j >= n; j--)
#define pb push_back
#define HashMap unordered_map
#define HashSet unordered_set
#define var auto
#define all(i) i.begin(), i.end()
#define all1(i) i.begin() + 1,i.end()
#define endl '\n'
#define px first
#define py second
#define DEBUG(a) cout<<a<<endl
using VI = vector<int>;
using VL = vector<long long>;
using ll = long long;
using ull = unsigned long long;
using db = double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template<class T1, class T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& p) {
out << '(' << p.first << ", " << p.second << ')';
return out;
}
template<typename T>
ostream& operator<<(ostream& out, const vector<T>& ve) {
for (T i : ve)
out << i << ' ';
return out;
}
template<class T1, class T2>
ostream& operator<<(ostream& out, const map<T1, T2>& mp) {
for (auto i : mp)
out << i << '\n';
return out;
}
const int INF = 0x3f3f3f3f;
const ll LNF = 0x3f3f3f3f3f3f3f3f;
const int IINF = 0x7fffffff;
const int iinf = 0x80000000;
const ll LINF = 0x7FFFFFFFFFFFFFFF;
const ll linf = 0x8000000000000000;
int dx[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };
int dy[8] = { 0, 0, 1, -1, 1, -1, -1, 1 };
//#include "Lynia.h"
namespace MyTools
{
template <typename T>
class Math
{
public:
static T gcd(T a, T b)
{
return b ? gcd(b, a % b) : a;
}
static T lcm(T a, T b)
{
return a / gcd(a, b) * b;
}
static T exgcd(T a, T b, T& x, T& y)
{
if (b == 0)
{
x = 1;
y = 0;
return a;
}
T d = exgcd(b, a % b, x, y);
T t = x;
x = y;
y = t - a / b * y;
return d;
}
static T lowbit(T k)
{
return k & (-k);
}
static T fastPow(T a, T n, T mod = 1e9 + 7)
{ // 快速幂
T ans = 1;
a %= mod;
while (n)
{
if (n & 1)
ans = (ans * a) % mod;
a = (a * a) % mod;
n >>= 1;
}
return ans;
}
static T inv(T x, T mod)
{ // 快速幂求逆
return fastPow(x, mod - 2, mod);
}
static vector<int> highPrecisionAdd(vector<int>& A, vector<int>& B)
{ // AB倒序输入
vector<int> C;
int t = 0; // 进位
for (int i = 0; i < A.size() || i < B.size(); i++)
{
if (i < A.size())
t += A[i];
if (i < B.size())
t += B[i];
C.push_back(t % 10);
t /= 10;
}
if (t)
C.push_back(1);
return C; // 倒序
}
static vector<long long> factorCount(int n)
{ // 计算1-n每个数的因子个数
vector<long long> factorsCnts(n + 1);
for (int i = 1; i <= n; i++)
for (int j = i; j <= n; j += i)
factorsCnts[j]++;
return factorsCnts;
}
static set<int> factorNumbers(int n)
{ // 统计n有哪些因子
set<int> factors;
for (int i = 1; i <= n / i; i++)
{
if (n % i == 0)
{
factors.insert(i);
if (i != n / i)
factors.insert(n / i);
}
}
return factors;
}
static map<int, int> primeFactorsMAP(int n)
{ // 分解质因数
map<int, int> mp;
int m = n;
for (int i = 2; i <= n / i; i++)
{
while (m % i == 0)
{
m /= i;
mp[i]++;
}
}
if (m > 1)
mp[m]++;
return mp;
}
static set<int> primeFactorsSET(int n)
{ // 分解质因数
set<int> se;
int m = n;
for (int i = 2; i <= n / i; i++)
{
while (m % i == 0)
{
m /= i;
se.insert(i);
}
}
if (m > 1)
se.insert(m);
return se;
}
static long long C(long long a, long long b, long long mod)
{
long ans = 1;
for (long long i = 1; i <= b; i++)
{
ans = ans * (a - i + 1) % mod * fastPow(i, mod - 2, mod) % mod;
}
return ans;
}
static string decimalToBinary(int n, bool flag = 0)
{ // flag是否返回倒转 如4:100 4:001
if (n == 0)
return "0";
string binaryNumber = "";
while (n > 0)
{
binaryNumber = to_string(n % 2) + binaryNumber;
n /= 2;
}
if (!flag)
return binaryNumber;
else
{
reverse(binaryNumber.begin(), binaryNumber.end());
return binaryNumber;
}
}
};
class EulerPrime
{
public:
int cnt = 0;
vector<int> prime;
EulerPrime(int n)
{
prime.assign(n + 1, 0);
vis.assign(n + 1, 0);
init(n);
}
bool isPrime(int n)
{
if (n == 1 || n == 0)
return 0;
return !vis[n];
}
map<int, int> primeFactorsMAP(int n)
{ // 分解质因数
map<int, int> mp;
int m = n;
for (int i : prime)
{
while (m % i == 0)
{
m /= i;
mp[i]++;
}
if (isPrime(m) or m == 1) break;
}
if (m > 1)
mp[m]++;
return mp;
}
vector<int> primeFactorsVEC(int n)
{ // 欧拉筛优化分解质因数 (防多测用)
vector<int> se;
int m = n;
for (int i : prime)
{
if (m % i == 0)se.push_back(i);
while (m % i == 0)m /= i;
if (isPrime(m) or m == 1) break;
}
if (m > 1)
se.push_back(m);
return se;
}
private:
vector<bool> vis;
void init(int n) // 欧拉筛
{
for (int i = 2; i <= n; i++)
{
if (!vis[i])
prime[cnt++] = i;
for (int j = 0; j < cnt && i * prime[j] <= n; j++)
{
vis[i * prime[j]] = 1; // 用最小质因数筛去
if (i % prime[j] == 0)
break; // 不是最小质因数
}
}
}
};
template <typename T>
class Combinatorics
{
private:
T mod;
T inv(T x)
{ // 快速幂求逆
return Math<T>::fastPow(x, mod - 2, mod);
}
void init(T N)
{ // 组合数计算初始化
fac[0] = 1;
for (T i = 1; i <= N; i++)
fac[i] = fac[i - 1] * i % mod;
}
public:
vector<T> fac; // 阶乘
Combinatorics(T N, T mod = 1e9 + 7) : mod(mod)
{
fac.assign(N + 1, 0);
init(N);
}
T C(T n, T m)
{ // 朴素组合数计算
if (m < 0 || n - m < 0)
return 0;
return fac[n] * inv(fac[m]) % mod * inv(fac[n - m]) % mod;
}
T lucas(T n, T m)
{ // 卢卡斯定理
return m == 0 ? 1 % mod : lucas(n / mod, m / mod) * C(n % mod, m % mod) % mod;
}
T Stirling2(ll n, ll m)
{ // 第二类斯特灵数：将一个有 n 个元素的集合分成 m 个非空的集合，求方案数。
if (m > n)
return 0; // n大于m
ll res = 0;
for (int i = 0; i <= m; i++)
{ // 通项公式
ll p = Math<T>::fastPow(i, n) * inv(fac[i]) % mod * inv(fac[m - i]) % mod;
if ((m - i) % 2)
res = (res + mod - p) % mod;
else
res = (res + p) % mod;
}
return res % mod;
}
};
template <class Info>
class SegmentTree
{ // 下标从 1 开始
#define l(p) (p << 1)
#define r(p) (p << 1 | 1)
protected:
int n;
vector<Info> info;
void init(int _n)
{
vector<Info> _now(_n + 1, Info());
init(_now);
}
void init(vector<Info>& _init)
{
n = _init.size() - 1;
info.assign(n << 2, Info()); // 为info开辟大小
auto build = [&](auto self, int p, int l, int r)
{
if (l == r)
{
info[p] = _init[l];
return;
}
int mid = l + r >> 1;
self(self, l(p), l, mid);
self(self, r(p), mid + 1, r);
pushup(p);
};
build(build, 1, 1, n);
}
void pushup(int p)
{
info[p] = info[l(p)] + info[r(p)];
}
public:
// 该模板在单点替换的题目中，运算符重载可能会出现一定错误，比如出现了 空值替换有值 (不必要的替换)
SegmentTree() : n(0) {};
SegmentTree(int _n)
{
init(_n);
}
SegmentTree(vector<Info>& _init)
{
init(_init);
}
template<typename Args> // 万能引用
void modify(int p, int pl, int pr, int x, Args&& v)
{
if (pl == pr)
{
// info[p] = v;
info[p].apply(v);
return;
}
int mid = pl + pr >> 1;
if (x <= mid)
modify(l(p), pl, mid, x, v);
else
modify(r(p), mid + 1, pr, x, v);
pushup(p);
}
void modify(int p, Info&& v)
{
modify(1, 1, n, p, forward<Info>(v)); // 完美转发
}
void modify(int p, Info& v)
{
modify(1, 1, n, p, forward<Info>(v)); // 完美转发
}
Info query(int L, int R, int p, int pl, int pr)
{
if (pl > R || pr < L)
return Info();
if (L <= pl && pr <= R)
return info[p];
int mid = pl + pr >> 1;
return query(L, R, l(p), pl, mid) + query(L, R, r(p), mid + 1, pr);
}
Info query(int L, int R)
{
return query(L, R, 1, 1, n);
}
#undef l(p)
#undef r(p)
};
template<class Info, class T>
class SegmentTree_BinarySearch : SegmentTree<Info> {
#define super SegmentTree<Info>
public:
SegmentTree_BinarySearch() : super::n(0) {};
SegmentTree_BinarySearch(int _n)
{
super::init(_n);
}
SegmentTree_BinarySearch(vector<Info>& _init)
{
super::init(_init);
}
int bin_search(int L, int R, const T& v);
void modify(int p, const Info& v = Info())
{
super::modify(p, v);
}
Info query(int L, int R)
{
return super::query(L, R);
}
#undef super
};
template <class Info, class Tag>
class LazySegmentTree
{
/* 该模板可能在直接相加的情况下比较好用，区间替换可能会出大大小小问题，这里写出区间替换模板
* 区间替换并求区间和板子
struct Tag {
ll newValue = 0;
bool f = 0; // 是否进行替换
Tag() {};
Tag(ll newValue, bool f = 0) :newValue(newValue), f(f) {};
void apply(Tag t) {
if (t.f) { // 这里很重要，因为这个板子初始化的时候就会调用 tag，所以这里上个 f 作为保险
f = 1;
newValue = t.newValue;
}
}
};
struct Info {
ll value = 0;
Info() {};
Info(ll value) :value(value) {};
void apply(Tag t, int len) {
if (t.f)
value = t.newValue * len;
}
};
Info operator+(Info a, Info b) {
Info c;
c.value = a.value + b.value;
return c;
}
void solve(int CASE)
{
int n; cin >> n;
auto a = vector<Info>(n + 1, Info());
fa(i, 1, n) {
ll now; cin >> now;
a[i].now = now;
}
// 初始化的时候自动会调用所有 Tag
MT::LazySegmentTree<Info, Tag> sg(a);
// 查看每个值
fa(i, 1, n) {
cout << sg.query(i, i).value << ' ';
}
cout << endl;
int q; cin >> q;
while (q--) {
ll l, r, x; cin >> l >> r >> x;
sg.modifyRange(l, r, Tag(x, 1));
// 查看更新后的每个值
fa(i, 1, n)
cout << sg.query(i, i).value << ' ';
cout << endl;
}
return;
}
*/
#define l(p) (p << 1)
#define r(p) (p << 1 | 1)
protected:
int n;
vector<Info> info;
vector<Tag> tag;
void init(int _n)
{
vector<Info> _now(_n + 1);
init(_now);
}
void init(vector<Info>& _init)
{
n = _init.size() - 1;
info.assign(n << 2, Info()); // 为info开辟大小
tag.assign(n << 2, Tag()); // 为tag开辟大小
auto build = [&](auto self, int p, int l, int r)
{
if (l == r)
{
info[p] = _init[l];
return;
}
int mid = l + r >> 1;
self(self, l(p), l, mid);
self(self, r(p), mid + 1, r);
pushup(p);
};
build(build, 1, 1, n);
}
void pushup(int p)
{
info[p] = info[l(p)] + info[r(p)];
}
void apply(int p, const Tag& v, int len)
{
info[p].apply(v, len);
tag[p].apply(v);
}
void pushdown(int p, int pl, int pr)
{ // 传入pl, pr计算区间长度
int mid = pl + pr >> 1;
apply(l(p), tag[p], mid - pl + 1);
apply(r(p), tag[p], pr - mid);
tag[p] = Tag(); // 设空
}
public:
LazySegmentTree() : n(0) {};
LazySegmentTree(int _n)
{
init(_n);
}
LazySegmentTree(vector<Info>& _init)
{
init(_init);
}
void modify(int p, int pl, int pr, int x, const Info& v = Info())
{ // 单点修改
if (pl == pr)
{
info[p] = v;
return;
}
int mid = pl + pr >> 1;
pushdown(p, pl, pr); // 传入pl, pr计算区间长度
if (x <= mid)
modify(l(p), pl, mid, x, v);
else
modify(r(p), mid + 1, pr, x, v);
pushup(p);
}
void modify(int p, const Info& v = Info())
{
modify(1, 1, n, p, v);
}
Info query(int L, int R, int p, int pl, int pr)
{
if (pl > R || pr < L)
return Info();
if (L <= pl && pr <= R)
return info[p];
int mid = pl + pr >> 1;
pushdown(p, pl, pr); // 传入pl, pr计算区间长度
return query(L, R, l(p), pl, mid) + query(L, R, r(p), mid + 1, pr);
}
Info query(int L, int R)
{
return query(L, R, 1, 1, n);
}
void modifyRange(int L, int R, int p, int pl, int pr, const Tag& v)
{ // 区间修改
if (pl > R || pr < L)
return;
if (L <= pl && pr <= R)
{
apply(p, v, pr - pl + 1); // 传入区间长度
return;
}
int mid = pl + pr >> 1;
pushdown(p, pl, pr); // 传入pl, pr计算区间长度
modifyRange(L, R, l(p), pl, mid, v);
modifyRange(L, R, r(p), mid + 1, pr, v);
pushup(p);
}
void modifyRange(int L, int R, const Tag& v)
{
return modifyRange(L, R, 1, 1, n, v);
}
#undef l(p)
#undef r(p)
};
template <class T>
class List
{
private:
vector<int> l, r;
map<T, int> pos;
int cnt = 1, tail = 0;
public:
vector<T> value;
List(int n = 2e5 + 10)
{ // 预留空间，默认2e6
value.assign(n * 10, 0);
l.assign(n * 10, 0);
r.assign(n * 10, 0);
}
void remove(int idx)
{
try
{
if (tail == 0)
throw runtime_error("list size is null");
if (idx > tail)
throw runtime_error("remove null pos");
}
catch (const std::exception& e)
{
cerr << e.what() << endl;
}
l[r[idx]] = l[idx];
r[l[idx]] = r[idx];
tail--;
}
void insert(int idx, T val)
{
value[cnt] = val;
pos[val] = cnt;
// 插入节点
l[cnt] = idx;
r[cnt] = r[idx];
l[r[idx]] = cnt;
r[idx] = cnt++;
tail++;
}
void push_back(T val)
{
value[cnt] = val;
pos[val] = cnt;
// 插入节点
l[cnt] = tail;
r[cnt] = r[tail];
l[r[tail]] = cnt;
r[tail] = cnt++;
tail++;
}
void print_all()
{
int k = tail;
for (int i = r[0]; k; i = r[i])
{
cout << value[i] << ' ';
k--;
}
}
};
template <typename T>
class ST
{
public:
static vector<T> Log2;
/* 构造 st 表前，先在类外定义 Log2，防止多次计算
template <typename T>
vector<T> ST<T>::Log2;
*/
ST(vector<T>& arr, int MAXN = 1e6 + 10)
{
// arr 从 1 开始
n = arr.size() - 1;
Min.assign(n + 1, vector<T>(21));
Max.assign(n + 1, vector<T>(21));
if (Log2.size() == 0) {
Log2.resize(MAXN);
log2_pre(MAXN);
}
build(arr);
}
T queryMin(int l, int r)
{ // 查询最小值
T s = Log2[r - l + 1];
return min(Min[l][s], Min[r - (1 << s) + 1][s]);
}
T queryMax(int l, int r)
{ // 查询最大值
T s = Log2[r - l + 1];
return max(Max[l][s], Max[r - (1 << s) + 1][s]);
}
private:
vector<vector<T>> Min, Max;
int n;
void log2_pre(int MAXN)
{ // 预处理log2
Log2[0] = -1;
for (int i = 1; i < MAXN; i++)
{
Log2[i] = Log2[i / 2] + 1;
}
}
void build(vector<T>& arr)
{ // 构建ST表
for (int i = 1; i <= n; i++)
{
Min[i][0] = Max[i][0] = arr[i];
}
for (int j = 1; j <= Log2[n]; j++)
{
for (int i = 1; i + (1 << j) - 1 <= n; i++)
{
Min[i][j] = min(Min[i][j - 1], Min[i + (1 << (j - 1))][j - 1]);
Max[i][j] = max(Max[i][j - 1], Max[i + (1 << (j - 1))][j - 1]);
}
}
}
};
template <typename T>
class BitTree
{ // 树状数组(优化的可操作前缀和)
public:
BitTree(int N)
{
n = N + 20;
t.assign(n, 0);
}
void update(T idx, const T& k)
{
for (T i = idx + 1; i <= n; i += lowbit(i))
t[i - 1] += k; // 运算符可改
}
T getsum(T idx)
{
T res = 0;
for (T i = idx + 1; i > 0; i -= lowbit(i))
res += t[i - 1]; // 运算符可改
return res;
}
T queryRange(int l, int r)
{
return getsum(r) - getsum(l - 1);
}
private:
vector<T> t; // 下标从0开始，实际上就是前缀和数组
int n;
T lowbit(T k) { return k & -k; }
};
class Manacher
{
public:
vector<int> lengths; // 以每个字符为中心的最长长度回文串的半径
int max_length = -1; // 最大回文长度
Manacher(string str)
{
int n = str.size();
init(str, n);
};
private:
void init(string str, int n)
{
// build
string s;
s.assign(n * 2 + 100, ' ');
str = ' ' + str;
int cnt = 0;
s[++cnt] = '~', s[++cnt] = '#';
for (int i = 1; i <= n; i++)
s[++cnt] = str[i], s[++cnt] = '#';
s[++cnt] = '!';
// solve
int mr = 0, mid = 0;
vector<int> p(n * 2 + 100);
for (int i = 2; i <= cnt - 1; i++)
{
if (i <= mr)
p[i] = min(p[mid * 2 - i], mr - i + 1);
else
p[i] = 1;
while (s[i - p[i]] == s[i + p[i]])
++p[i];
if (i + p[i] > mr)
mr = i + p[i] - 1, mid = i;
// 更新最大回文长度
max_length = max(max_length, p[i]);
// 放最大回文长度
if (s[i] != '#' && s[i] != '~' && s[i] != '!')
lengths.push_back(p[i] - 1);
}
max_length--;
}
};
class DoubleHashString
{
private:
#define ll long long
#define pll pair<long, long>
vector<ll> hs1, bs1, hs2, bs2;
// const int mod1 = 2147483647;
// const int mod2 = 1000000007;
// int generateRandomBase(int mod) {
// random_device rd;
// mt19937 gen(rd());
// uniform_int_distribution<> dis(1, mod - 1);
// return dis(gen);
// }
// const int base1 = generateRandomBase(mod1);
// const int base2 = generateRandomBase(mod2);
const int base1 = 233; // 第一个质数基数
const int base2 = 131; // 第二个质数基数
const ll mod1 = 1e9 + 13; // 第一个模数
const ll mod2 = 998244353; // 第二个模数
public:
// 初始化函数，预计算质数基数的幂次
DoubleHashString(const string& s)
{
// s 下标从 0 开始，l r 查询下标从 1 开始
int n = s.size();
hs1.resize(n + 1);
bs1.resize(n + 1);
hs2.resize(n + 1);
bs2.resize(n + 1);
hs1[0] = hs2[0] = 0;
bs1[0] = bs2[0] = 1;
for (int i = 1; i <= n; i++)
{
bs1[i] = (bs1[i - 1] * base1) % mod1;
bs2[i] = (bs2[i - 1] * base2) % mod2;
hs1[i] = (hs1[i - 1] * base1 + s[i - 1] - 'a' + 1) % mod1;
hs2[i] = (hs2[i - 1] * base2 + s[i - 1] - 'a' + 1) % mod2;
}
}
// 获取子串的双哈希值
pll get(int l, int r)
{
ll x = ((hs1[r] - hs1[l - 1] * bs1[r - l + 1]) % mod1 + mod1) % mod1;
ll y = ((hs2[r] - hs2[l - 1] * bs2[r - l + 1]) % mod2 + mod2) % mod2;
return make_pair(x, y);
}
#undef ll
#undef pll
};
class SingleHashString
{ // 自然溢出单哈希
private:
#define ull unsigned long long
vector<ull> hs, p;
const int base = 131;
public:
SingleHashString(string s)
{
// s 下标从 0 开始，l r 查询下标从 1 开始
hs.resize(s.size() + 10), p.resize(s.size() + 10);
s = ' ' + s;
p[0] = 1;
for (int i = 1; i < s.size(); i++)
{
hs[i] = hs[i - 1] * base + s[i] - 'a' + 1;
p[i] = p[i - 1] * base;
}
}
ull get(int l, int r)
{
return hs[r] - hs[l - 1] * p[r - l + 1];
}
#undef ull
};
template <class T>
class LCA
{
public:
vector<int> depth;
// vector<int>w; 树上边差分没准能用上，w[to] 表示 to 到其 fa 节点的边
LCA(int n, vector<vector<int>>& e)
{
f.assign(n + 10, vector<int>(31));
depth.assign(n + 10, 0);
// w.assign(n + 10, 0);
init(1, 0, e); // 邻接表
}
int lca(int x, int y)
{
if (depth[x] < depth[y])
swap(x, y);
// 后面进行x节点默认比y节点深
for (int i = 29; i >= 0; i--)
if (depth[x] - (1 << i) >= depth[y])
x = f[x][i];
if (x == y)
return x; // 特判：y就是原本x的祖宗
for (int i = 29; i >= 0; i--)
if (f[x][i] != f[y][i]) // 说明还没找到祖宗，更新a、b后接着跳
x = f[x][i], y = f[y][i];
return f[x][0];
}
private:
vector<vector<int>> f; // f[x][i]即x的第2^i个祖先 (31是倍增用的，最大跳跃为2^30)
void init(int now, int fa, vector<vector<int>>& e) // 邻接表
{
depth[now] = depth[fa] + 1;
f[now][0] = fa; // 第一个祖先
for (int i = 1; (1 << i) <= depth[now]; i++) // 求now的各个祖先
f[now][i] = f[f[now][i - 1]][i - 1];
for (int to : e[now])
{ // now这个的点的祖先都找完了，dfs处理别的点
if (to == fa)
continue;
init(to, now, e);
// w[to] = e[i].w;
}
}
};
template <const int T>
class ModInt
{
private:
const static int mod = T;
public:
int x;
ModInt(int x = 0) : x(x% mod) {}
ModInt(long long x) : x(int(x% mod)) {}
int val() { return x; }
ModInt operator+(const ModInt& a) const
{
int x0 = x + a.x;
return ModInt(x0 < mod ? x0 : x0 - mod);
}
ModInt operator-(const ModInt& a) const
{
int x0 = x - a.x;
return ModInt(x0 < 0 ? x0 + mod : x0);
}
ModInt operator*(const ModInt& a) const { return ModInt(1LL * x * a.x % mod); }
ModInt operator/(const ModInt& a) const { return *this * a.inv(); }
bool operator==(const ModInt& a) const { return x == a.x; };
bool operator!=(const ModInt& a) const { return x != a.x; };
void operator+=(const ModInt& a)
{
x += a.x;
if (x >= mod)
x -= mod;
}
void operator-=(const ModInt& a)
{
x -= a.x;
if (x < 0)
x += mod;
}
void operator*=(const ModInt& a) { x = 1LL * x * a.x % mod; }
void operator/=(const ModInt& a) { *this = *this / a; }
friend ModInt operator+(int y, const ModInt& a)
{
int x0 = y + a.x;
return ModInt(x0 < mod ? x0 : x0 - mod);
}
friend ModInt operator-(int y, const ModInt& a)
{
int x0 = y - a.x;
return ModInt(x0 < 0 ? x0 + mod : x0);
}
friend ModInt operator*(int y, const ModInt& a) { return ModInt(1LL * y * a.x % mod); }
friend ModInt operator/(int y, const ModInt& a) { return ModInt(y) / a; }
friend ostream& operator<<(ostream& os, const ModInt& a) { return os << a.x; }
friend istream& operator>>(istream& is, ModInt& t) { return is >> t.x; }
ModInt pow(long long n) const
{
ModInt res(1), mul(x);
while (n)
{
if (n & 1)
res *= mul;
mul *= mul;
n >>= 1;
}
return res;
}
ModInt inv() const
{
int a = x, b = mod, u = 1, v = 0;
while (b)
{
int t = a / b;
a -= t * b;
swap(a, b);
u -= t * v;
swap(u, v);
}
if (u < 0)
u += mod;
return u;
}
};
static int kmp(string& t, string& s)
{ // 在文本串 t 中找到模式串 s 出现的次数
// build
int nn = s.size();
vector<int> nt(nn);
for (int i = 1; i < nn; i++)
{
int j = nt[i - 1];
while (j > 0 && s[i] != s[j])
j = nt[j - 1];
if (s[i] == s[j])
j += 1;
nt[i] = j;
}
// kmp
int n = t.size(), m = s.size(), j = 0;
int last = -1e9, ans = 0;
for (int i = 0; i < n; i++)
{
while (j > 0 && t[i] != s[j])
j = nt[j - 1];
if (t[i] == s[j])
j += 1;
if (j == m)
{
int head = i - m + 1;
if (head >= last + m)
{
ans += 1;
last = head;
}
}
}
return ans;
}
class KMP
{
private:
vector<int> nt;
string s;
public:
// 在文本串 t 中找到模式串 s 出现的次数
// 存入模式串 s
KMP(string& s) : s(s)
{
int n = s.size();
nt.resize(n);
for (int i = 1; i < n; i++)
{
int j = nt[i - 1];
while (j > 0 && s[i] != s[j])
j = nt[j - 1];
if (s[i] == s[j])
j += 1;
nt[i] = j;
}
}
// 查询文本串 t
int kmp(string& t)
{
int n = t.size(), m = s.size(), j = 0;
int last = -1e9, ans = 0;
for (int i = 0; i < n; i++)
{
while (j > 0 && t[i] != s[j])
j = nt[j - 1];
if (t[i] == s[j])
j += 1;
if (j == m)
{
int head = i - m + 1;
if (head >= last + m)
{
ans += 1;
last = head;
}
}
}
return ans;
}
};
class ACAutomaton {
private:
int cnt = 1;
vector<int>in;
struct kkk {
int son[26] = { 0 }; // 子节点
int fail = 0; // 失败指针
int flag = 0; // 模式串起点
int ans = 0; // 当前节点匹配次数
void clear() {
memset(son, 0, sizeof(son));
fail = flag = ans = 0;
}
};
vector<kkk>trie; // Trie树
// 拓扑排序优化
void topu() {
queue<int>q;
for (int i = 1; i <= cnt; i++)
if (!in[i])q.push(i);
while (!q.empty()) {
int u = q.front();
q.pop();
output[trie[u].flag] = trie[u].ans; // 更新输出
int v = trie[u].fail;
in[v]--;
trie[v].ans += trie[u].ans;
if (!in[v])q.push(v);
}
}
int MAXN;
int ASCII_SIZE = 26;
public:
vector<int>Map; // 模式串下标 对应的 模式串起点的节点
vector<int>output; // 模式串起点的节点 对应的 模式串在文本串中出现的个数
// ASCII_SIZE : 26、52、128
ACAutomaton(int MAXN, int ASCII_SIZE = 26) :MAXN(MAXN), ASCII_SIZE(ASCII_SIZE),
in(MAXN + 10, 0), Map(MAXN + 10, 0), output(MAXN + 10, 0), trie(MAXN + 10) {}
void clear() { // ( 这个 clear 可能有些问题 )
for (int i = 0; i < MAXN + 5; i++) {
Map[i] = in[i] = output[i] = 0;
trie[i].clear();
}
}
// 插入模式串
void insert(string& s, int num) {
int u = 1, len = s.size();
for (int i = 0; i < len; i++) {
int v = s[i] - ((ASCII_SIZE <= 52) ? 'a' : 0);
if (!trie[u].son[v])trie[u].son[v] = ++cnt;
u = trie[u].son[v];
}
if (!trie[u].flag)trie[u].flag = num; // 模式串起点赋值
Map[num] = trie[u].flag;
}
// 构建失败指针
void getFail() {
queue<int>q;
for (int i = 0; i < ASCII_SIZE; i++)trie[0].son[i] = 1;
q.push(1);
while (!q.empty()) {
int u = q.front();
q.pop();
int Fail = trie[u].fail;
for (int i = 0; i < ASCII_SIZE; i++) {
int v = trie[u].son[i];
if (!v) {
trie[u].son[i] = trie[Fail].son[i];
continue;
}
trie[v].fail = trie[Fail].son[i];
in[trie[v].fail]++;
q.push(v);
}
}
}
// 查询文本串
void query(string& s) {
int u = 1, len = s.size();
for (int i = 0; i < len; i++)
u = trie[u].son[s[i] - ((ASCII_SIZE <= 52) ? 'a' : 0)], trie[u].ans++;
topu();
}
};
template<typename T>
class MinCostMaxFlow {
public:
// 边的结构体
struct Edge {
int to; // 目标节点
T cap; // 边的容量
T cost; // 边的费用
int rev; // 反向边在邻接表中的索引
};
// 构造函数，初始化节点数
MinCostMaxFlow(int n) : n(n), graph(n + 1), dist(n + 1), prevv(n + 1), preve(n + 1), h(n + 1) {}
// 添加边
void addEdge(int from, int to, T cap, T cost = 0) {
graph[from].push_back(Edge{ to, cap, cost, (int)graph[to].size() });
graph[to].push_back(Edge{ from, 0, -cost, (int)graph[from].size() - 1 });
}
// 计算最小费用最大流的函数
T minCostMaxFlow(int s, int t, T& flow) {
T res = 0; // 最小费用
fill(h.begin(), h.end(), 0); // 初始化势能数组
while (true) {
// 使用优先队列实现的Dijkstra算法
priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> pq;
fill(dist.begin(), dist.end(), INF); // 初始化距离数组
dist[s] = 0;
pq.push({ 0, s });
while (!pq.empty()) {
auto [d, v] = pq.top();
pq.pop();
if (dist[v] < d) continue;
for (int i = 0; i < graph[v].size(); ++i) {
Edge& e = graph[v][i];
if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {
dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
prevv[e.to] = v;
preve[e.to] = i;
pq.push({ dist[e.to], e.to });
}
}
}
if (dist[t] == INF) break; // 如果无法到达汇点，结束
for (int i = 0; i <= n; ++i) h[i] += dist[i]; // 更新势能
T d = INF;
for (int v = t; v != s; v = prevv[v]) {
d = min(d, graph[prevv[v]][preve[v]].cap); // 找到增广路径上的最小容量
}
flow += d; // 增加总流量
res += d * h[t]; // 增加总费用
for (int v = t; v != s; v = prevv[v]) {
Edge& e = graph[prevv[v]][preve[v]];
e.cap -= d; // 更新正向边的容量
graph[v][e.rev].cap += d; // 更新反向边的容量
}
}
return res; // 返回最小费用
}
private:
int n; // 节点数
const int INF = 1e9; // 定义无穷大
vector<vector<Edge>> graph; // 邻接表表示的图
vector<T> dist; // 最短路径费用
vector<int> prevv; // 前驱节点
vector<int> preve; // 前驱边
vector<T> h; // 势能数组
};
class XorBase {
private:
vector<long long> a; // 线性基基底
const int MN = 62;
bool flag = false;
public:
XorBase() :a(70, 0) {};
void print() {
for (int i : a)
cout << i << ' ';
cout << endl;
}
// XorBase[x]：说明第 x 位上存在代表性数 XorBase[x]
// 这个代表数的特点就是，最高位即为 2 ^ x
long long& operator[](int x) {
return a[x];
}
// 清除基底
void clear() {
a.clear();
}
// 插入新数
void insert(long long x) {
for (int i = MN; ~i; i--)
if (x & (1ll << i))
if (!a[i]) { a[i] = x; return; }
else x ^= a[i];
flag = true;
}
// 插入新数
void operator +=(long long x) {
insert(x);
}
// 线性基合并
void operator +=(XorBase& x) {
for (int i = MN; i >= 0; i--)if (x[i])*this += x[i];
}
friend XorBase operator +(XorBase& x, XorBase& y) {
XorBase z = x;
for (int i = 62; i >= 0; i--)if (y[i])z += y[i];
return z;
}
// 查是否存在线性基内
bool check(long long x) {
for (int i = MN; ~i; i--)
if (x & (1ll << i))
if (!a[i])return false;
else x ^= a[i];
return true;
}
// 查最大
long long qmax(long long res = 0) {
for (int i = MN; ~i; i--)
res = max(res, res ^ a[i]);
return res;
}
// 查最小
long long qmin() {
if (flag)return 0;
for (int i = 0; i <= MN; i++)
if (a[i])return a[i];
}
// 查询第 k 小
long long query(long long k) {
long long tmp[70] = { 0 };
long long res = 0; int cnt = 0;
k -= flag; if (!k)return 0;
for (int i = 0; i <= MN; i++) {
for (int j = i - 1; ~j; j--)
if (a[i] & (1ll << j))a[i] ^= a[j];
if (a[i])tmp[cnt++] = a[i];
}
if (k >= (1ll << cnt))return -1;
for (int i = 0; i < cnt; i++)
if (k & (1ll << i))res ^= tmp[i];
return res;
}
};
template<typename T>
class fast {
public:
// 使用 __int128 直接传入 T = __int128 就行
inline static T in()
{
T x = 0, f = 1;
char ch = getchar();
while (ch < '0' || ch>'9')
{
if (ch == '-')
f = -1;
ch = getchar();
}
while (ch >= '0' && ch <= '9')
x = x * 10 + ch - '0', ch = getchar();
return x * f;
}
static void out(T x)
{
if (x < 0)
putchar('-'), x = -x;
if (x > 9)
out(x / 10);
putchar(x % 10 + '0');
return;
}
static void outln(T x)
{
out(x);
putchar('\n');
}
};
class PersistentSegmemtTree {
// 可持久化权值线段树(主席树)
// 可能需要离散化，根据离散化数组进行初始化
// 下标从 1 开始
/* 求第 k 小模板
int n, m; cin >> n >> m;
auto a = vector<int>(n + 1);
auto b = vector<int>();
fa(i, 1, n)cin >> a[i], b.pb(a[i]);
sort(all(b));
b.erase(unique(all(b)), b.end());
int len = b.size();
PersistentSegmemtTree sg(len, n);
auto find = [&](int value)->int {
return upper_bound(all(b), value) - b.begin();
};
// 初始化主席树，记得赋值
fa(i, 1, n) sg.root[i] = sg.update(find(a[i]), 1, sg.root[i - 1]);
while (m--) {
int l, r, k; cin >> l >> r >> k;
// 求区间相减，传入 l - 1
cout << b[sg.query_k_min(l - 1, r, k) - 1] << endl;
}
*/
/* 求区间多少不同元素模板
int n; cin >> n;
PersistentSegmemtTree sg(n, n);
HashMap<int, int>mp;
fa(i, 1, n) {
int x; cin >> x;
if (mp.count(x)) {
// 如果之前出现过，且出现在 mp[x] 位置，
// 就删掉之前出现的，转而把这个值放在现在的 i 上，
// 这样能保证每个线段树都存在这个数，同时也不会重复
int t = sg.update(mp[x], -1, sg.root[i - 1]);
sg.root[i] = sg.update(i, 1, t);
}
else sg.root[i] = sg.update(i, 1, sg.root[i - 1]);
mp[x] = i;
}
int m; cin >> m;
while (m--) {
int l, r; cin >> l >> r;
cout << sg.query(l, r) << endl;
}
*/
private:
int tot = 0;
struct tree { int l = 0, r = 0, sum = 0; };
vector<tree>t;
int len;
int build(int l, int r) { // 初始化建树，建 len 个节点的
int node = ++tot;
if (l == r)return node;
int mid = l + r >> 1;
t[node].l = build(l, mid);
t[node].r = build(mid + 1, r);
return node;
}
public:
vector<int>root;
// m 传入实际离散化后大小即可，不用 + 1
// n 传入离散化前的个数
PersistentSegmemtTree(int m, int n) :len(m), t((n << 6) + 10), root(n + 10) {
root[0] = build(1, len);
}
// 主席树的更新继承上一个线段树的根节点
int update(int l, int r, int pos, int value, int pre) {
int node = ++tot;
t[node] = t[pre];
t[node].sum += value;
if (l == r)return node;
int mid = l + r >> 1;
if (pos <= mid) // 新的左子节点会继承前一个版本的左子节点进行更新
t[node].l = update(l, mid, pos, value, t[pre].l);
else // 同理
t[node].r = update(mid + 1, r, pos, value, t[pre].r);
return node;
}
// 传入离散化数组对应的下标，更新的值，上一个已更新的线段树的根节点
int update(int pos, int value, int pre) {
return update(1, len, pos, value, pre);
}
// update 是加，change 是直接改变
int change(int l, int r, int pos, int value, int pre) {
int node = ++tot;
t[node] = t[pre];
t[node].sum = value;
if (l == r)return node;
int mid = l + r >> 1;
if (pos <= mid)
t[node].l = change(l, mid, pos, value, t[pre].l);
else
t[node].r = change(mid + 1, r, pos, value, t[pre].r);
return node;
}
int change(int pos, int value, int pre) {
return change(1, len, pos, value, pre);
}
// 本质其实是同时算两个权值线段树在 [1, l] 和 [1, r] 两个区间查询
int query_k_min(int u, int v, int l, int r, int k) {
int mid = l + r >> 1;
// 通过区间减法得左儿子中存的数值个数
int lnum = t[t[v].l].sum - t[t[u].l].sum;
if (l == r)return l;
if (k <= lnum) // 第 k 小在左子
return query_k_min(t[u].l, t[v].l, l, mid, k);
else // 第 k 小在右子，并注意相减
return query_k_min(t[u].r, t[v].r, mid + 1, r, k - lnum);
}
// 原理是前缀和，要传入 L - 1
int query_k_min(int L, int R, int k) {
return query_k_min(root[L], root[R], 1, len, k);
}
// 朴素区间查询，但只需要传入一棵树
int queryRange(int l, int r, int L, int R, int pre) {
if (L <= l and r <= R) return t[pre].sum;
int mid = l + r >> 1;
int res = 0;
if (L <= mid)res += queryRange(l, mid, L, R, t[pre].l);
if (R > mid)res += queryRange(mid + 1, r, L, R, t[pre].r);
return res;
}
// v 为线段树版本，注意这个版本必须大于等于 R
int queryRange(int L, int R, int v = -1) {
if (v == -1)v = root[R];
// 这里只会传入一个线段树版本然后接着朴素查询
return queryRange(1, len, L, R, v);
}
};
template<typename T = long long>
class Frac
{
private:
T abs(const T& x)const { return x < 0 ? -x : x; }
T gcd(const T& x, const T& y)const { return y ? gcd(y, x % y) : x; }
Frac reduce()
{
bool flag = 0;
if (a < 0 && b < 0) a = -a, b = -b;
if (a < 0) a = -a, flag = 1;
if (b < 0) b = -b, flag = 1;
T ggcd = gcd(a, b);
a /= ggcd;
b /= ggcd;
if (flag) a = -a;
return *this;
}
void swap() { std::swap(a, b); }
Frac _swap(const Frac& t)const { return Frac(t.b, t.a); }
T FastPow(T x, T p, T mod)const
{
T ans = 1, bas = x;
for (; p; bas = bas * bas % mod, p >>= 1)
if (p & 1) ans = ans * bas % mod;
return ans;
}
public:
T a, b;
Frac(T A = 0, T B = 1) { a = A, b = B; }
T to_inv(const T& mod = 1e9 + 7)const { return a * FastPow(b, mod - 2, mod) % mod; }
Frac abs()const { return Frac(abs(a), abs(b)); }
friend ostream& operator<<(ostream& out, const Frac& a) { out << a.a << ' ' << a.b; return out; }
Frac operator =(const Frac& t) { return a = t.a, b = t.b, t; }
bool operator ==(const Frac& t)const { Frac A(*this), B(t); return (A.reduce().a == B.reduce().a) && (A.b == B.b); }
bool operator !=(const Frac& t)const { Frac A(*this), B(t); return (A.a != B.a) || (A.b != B.b); }
bool operator >(const Frac& t)const { Frac A(*this), B(t); T ggcd = gcd(A.reduce().b, B.reduce().b); return B.b / ggcd * A.a > A.b / ggcd * B.a; }
bool operator <(const Frac& t)const { Frac A(*this), B(t); T ggcd = gcd(A.reduce().b, B.reduce().b); return B.b / ggcd * A.a < A.b / ggcd * B.a; }
bool operator >=(const Frac& t)const { Frac A(*this), B(t); T ggcd = gcd(A.reduce().b, B.reduce().b); return B.b / ggcd * A.a >= A.b / ggcd * B.a; }
bool operator <=(const Frac& t)const { Frac A(*this), B(t); T ggcd = gcd(A.reduce().b, B.reduce().b); return B.b / ggcd * A.a <= A.b / ggcd * B.a; }
Frac operator +(const Frac& t)const { T ggcd = gcd(b, t.b); return Frac(b / ggcd * t.a + t.b / ggcd * a, b / ggcd * t.b).reduce(); }
Frac operator +=(const Frac& t) { return *this = *this + t; }
Frac operator *(const Frac& t)const { return Frac(a * t.a, b * t.b).reduce(); }
Frac operator *=(const Frac& t) { return *this = *this * t; }
Frac operator -(const Frac& t)const { return (*this + Frac(-t.a, t.b)).reduce(); }
Frac operator -=(const Frac& t) { return *this = *this - t; }
Frac operator /(const Frac& t)const { return (t._swap(t) * (*this)).reduce(); }
Frac operator /=(const Frac& t) { return *this = *this / t; }
Frac operator -()const { return Frac(-a, b); }
};
//////// CalGeo ////////
template<typename T>
class Point;
template<typename T>
class Line;
template<typename T>
class Polygon;
template<typename T>
class Circle;
template<typename T>
using Vector = Point<T>;
template<typename T>
using Segment = Line<T>;
namespace Geo {
const double eps = 1e-8;
const double PI = acos(-1.0);
// 浮点数 x 的符号
template<typename T>
int sgn(T x) {
if (fabs(x) < eps) return 0;
return x > 0 ? 1 : -1;
}
// 比较两个浮点数
template<typename T>
int cmp(T x, T y) {
if (fabs(x) < eps)return 0; // x == y，返回 0
else return x < y ? -1 : 1; // x < y，返回 -1; x > y，返回 1
}
// 两点距离
template<typename T>
T dist(const Point<T>& A, const Point<T>& B) {
return sqrt((A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y));
}
// 点积
template<typename T>
T dot(const Vector<T>& A, const Vector<T>& B) {
return A.x * B.x + A.y * B.y;
}
// 叉积
template<typename T>
T cross(const Vector<T>& A, const Vector<T>& B) {
return A.x * B.y - A.y * B.x;
}
// 向量长度
template<typename T>
T len(const Vector<T>& A) {
return sqrt(dot(A, A));
}
// 向量长度的平方
template<typename T>
T len2(const Vector<T>& A) {
return dot(A, A);
}
// 两向量夹角
template<typename T>
double angle(const Vector<T>& A, const Vector<T>& B) {
return acos(dot(A, B) / len(A) / len(B));
}
// 计算两向量构成的平行四边形有向面积
// 三个点A、B、C，以A为公共点，得到2个向量B-A和C-A，它们构成的平行四边形
template<typename T>
T area2(const Point<T>& A, const Point<T>& B, const Point<T>& C) {
return cross(B - A, C - A);
}
// 向量旋转
/*
特殊情况是旋转90度：
逆时针旋转90度：Rotate(A, pi/2)，返回Vector(-A.y, A.x)；
顺时针旋转90度：Rotate(A, -pi/2)，返回Vector(A.y, - A.x)。
*/
template<typename T>
Vector<T> rotate(const Vector<T>& A, double rad) {
return Vector<T>(A.x * cos(rad) - A.y * sin(rad), A.x * sin(rad) + A.y * cos(rad));
}
// 有时需要求单位法向量，即逆时针转90度，然后取单位值。
template<typename T>
Vector<T> normal(const Vector<T>& A) {
return Vector<T>(-A.y / len(A), A.x / len(A));
}
// 两个向量是否平行或重合
template<typename T>
bool parallel(const Vector<T>& A, const Vector<T>& B) {
return sgn(cross(A, B)) == 0; // 返回true表示平行或重合
}
// 点和直线的位置关系
template<typename T>
int point_line_relation(const Point<T>& p, const Line<T>& v) {
int c = sgn(cross(p - v.p1, v.p2 - v.p1));
if (c < 0)return 1; // 1 ：p在v的左边
if (c > 0)return 2; // 2 ：p在v的右边
return 0; // 0 ：p在v上
}
// 点和线段的位置关系
template<typename T>
bool point_is_on_segment(const Point<T>& p, const Line<T>& v) { // 点和线段：0 点不在线段v上；1 点在线段v上
return sgn(cross(p - v.p1, v.p2 - v.p1)) == 0 && sgn(dot(p - v.p1, p - v.p2)) <= 0;
}
// 点到直线的距离
template<typename T>
double point_line_dis(const Point<T>& p, const Line<T>& v) {
return fabs(cross(p - v.p1, v.p2 - v.p1)) / dist(v.p1, v.p2);
}
// 点在直线上的投影
template<typename T>
Point<T> point_line_proj(const Point<T>& p, const Line<T>& v) {
double k = dot(v.p2 - v.p1, p - v.p1) / Len2(v.p2 - v.p1);
return v.p1 + (v.p2 - v.p1) * k;
}
// 点关于直线的对称点
template<typename T>
Point<T> point_line_symmetry(const Point<T>& p, const Line<T>& v) {
Point<T> q = point_line_proj(p, v);
return Point<T>(2 * q.x - p.x, 2 * q.y - p.y);
}
// 点到线段的距离
template<typename T>
double point_segment_dis(const Point<T>& p, const Segment<T>& v) {
if (sgn(dot(p - v.p1, v.p2 - v.p1)) < 0 || sgn(dot(p - v.p2, v.p1 - v.p2)) < 0)
return min(dist(p, v.p1), dist(p, v.p2));
return point_line_dis(p, v); // 点的投影在线段上
}
// 叉积判断两条向量的位置关系，AB * AC，两向量共点
template<typename T>
int vector_vector_relation(const Vector<T>& v1, const Vector<T>& v2) {
int sign = sgn(cross(v1, v2));
if (sign == 0)return 0; // 共线
if (sign > 0)return 1; // v2 在 v1 的逆时针方向
if (sign < 0)return 2; // v2 在 v1 的顺时针方向
}
// 叉积判断两条直线的位置关系
template<typename T>
int line_line_relation(const Line<T>& v1, const Line<T>& v2) {
if (sgn(cross(v1.p2 - v1.p1, v2.p2 - v2.p1)) == 0) {
if (point_line_relation(v1.p1, v2) == 0) return 1; // 1: 重合
else return 0; // 0: 平行
}
return 2; // 2: 相交
}
// 两条直线的交点
template<typename T>
Point<T> line_line_cross_point(const Point<T>& a, const Point<T>& b, const Point<T>& c, const Point<T>& d) {
// Line1 : ab, Line2 : cd
double s1 = cross(b - a, c - a);
double s2 = cross(b - a, d - a); // 叉积有正负
return Point<T>(c.x * s2 - d.x * s1, c.y * s2 - d.y * s1) / (s2 - s1);
}
// 两个线段是否相交
template<typename T>
bool segment_segment_is_cross(const Point<T>& a, const Point<T>& b, const Point<T>& c, const Point<T>& d) {
// Line1 : ab, Line2 : cd
double c1 = cross(b - a, c - a), c2 = cross(b - a, d - a);
double d1 = cross(d - c, a - c), d2 = cross(d - c, b - c);
return sgn(c1) * sgn(c2) < 0 && sgn(d1) * sgn(d2) < 0; // 1: 相交；0: 不相交
}
// 点和多边形的关系
template<typename T>
int point_polygon_relation(const Point<T>& pt, const Polygon<T>& p) {
// 点pt，多边形 p
int n = p.size();
for (int i = 0; i < n; i++) {
if (p[i] == pt) return 3; // 3：点在多边形的顶点上
}
for (int i = 0; i < n; i++) {
Line<T> v = Line<T>(p[i], p[(i + 1) % n]);
if (point_is_on_segment(pt, v)) return 2; // 2：点在多边形的边上
}
int num = 0;
for (int i = 0; i < n; i++) {
int j = (i + 1) % n;
int c = sgn(cross(pt - p[j], p[i] - p[j]));
int u = sgn(p[i].y - pt.y);
int v = sgn(p[j].y - pt.y);
if (c > 0 && u < 0 && v >= 0) num++;
if (c < 0 && u >= 0 && v < 0) num--;
}
return num != 0; // 1：点在内部; 0：点在外部
}
// 计算多边形周长
template<typename T>
T polygon_perimeter(const Polygon<T>& p) {
T ans = 0;
int n = p.size();
for (int i = 0; i < n; i++)
ans += dist(p[i], p[(i + 1) % n]);
return ans;
}
// 多边形的面积
template<typename T>
T polygon_area(const Polygon<T>& p) {
T area = 0;
int n = p.size();
for (int i = 0; i < n; i++)
area += cross(p[i], p[(i + 1) % n]);
return area / 2; // 面积有正负，返回时不能简单地取绝对值
}
// 多边形的重心
template<typename T>
Point<T> polygon_center_point(const Polygon<T>& p) { //求多边形重心
Point<T> ans(0, 0);
int n = p.size();
if (polygon_area(p, n) == 0) return ans;
for (int i = 0; i < n; i++)
ans = ans + (p[i] + p[(i + 1) % n]) * cross(p[i], p[(i + 1) % n]);
return ans / polygon_area(p, n) / 6;
}
// 求凸包，凸包顶点放在ch中
// 凸多边形：是指所有内角大小都在 [0, 180] 范围内的简单多边形
// 凸包：在平面上能包含所有给定点的最小凸多边形叫做凸包
template<typename T>
Polygon<T> convex_hull(const vector<Point<T>>& p) {
Polygon<T> ch;
int n = p.size();
n = unique(p.begin(), p.end()) - p; // 去除重复点
ch.resize(n);
sort(p.begin(), p.begin() + n); // 对点排序：按 x 从小到大排序，如果 x 相同，按 y 排序
int v = 0;
// 求下凸包，如果p[i]是右拐弯的，这个点不在凸包上，往回退
for (int i = 0; i < n; i++) {
while (v > 1 && sgn(cross(ch[v - 1] - ch[v - 2], p[i] - ch[v - 1])) <= 0) // 把后面 ch[v-1] 改成 ch[v-2] 也行
v--;
ch[v++] = p[i];
}
int j = v;
// 求上凸包
for (int i = n - 2; i >= 0; i--) {
while (v > j && sgn(cross(ch[v - 1] - ch[v - 2], p[i] - ch[v - 1])) <= 0) // 把后面 ch[v-1] 改成 ch[v-2] 也行
v--;
ch[v++] = p[i];
}
ch.erase(unique(ch.begin(), ch.end()), ch.end());
return ch;
}
// 点和圆的关系，根据点到圆心的距离判断
template<typename T>
int point_circle_relation(const Point<T>& p, const Circle<T>& C) {
double dst = dist(p, C.c);
if (sgn(dst - C.r) < 0) return 0; // 0: 点在圆内
if (sgn(dst - C.r) == 0) return 1; // 1: 圆上
return 2; // 2: 圆外
}
// 直线和圆的关系，根据圆心到直线的距离判断
template<typename T>
int line_circle_relation(const Line<T>& v, const Circle<T>& C) {
double dst = point_line_dis(C.c, v);
if (sgn(dst - C.r) < 0) return 0; // 0: 直线和圆相交
if (sgn(dst - C.r) == 0) return 1; // 1: 直线和圆相切
return 2; // 2: 直线在圆外
}
// 线段和圆的关系，根据圆心到线段的距离判断
template<typename T>
int segment_circle_relation(const Segment<T> v, const Circle<T> C) {
double dst = point_segment_dis(C.c, v);
if (sgn(dst - C.r) < 0) return 0; // 0: 线段在圆内
if (sgn(dst - C.r) == 0) return 1; // 1: 线段和圆相切
return 2; // 2: 线段在圆外
}
//pa, pb是交点。返回值是交点个数
template<typename T>
int line_cross_circle(const Line<T>& v, const Circle<T>& C, Point<T>& p1, Point<T>& p2) {
if (line_circle_relation(v, C) == 2) return 0; // 无交点
Point<T> q = point_line_proj(C.c, v); // 圆心在直线上的投影点
double d = point_line_dis(C.c, v); // 圆心到直线的距离
double k = sqrt(C.r * C.r - d * d);
if (sgn(k) == 0) { // 1个交点，直线和圆相切
p1 = q; p2 = q; return 1;
}
Point<T> n = (v.p2 - v.p1) / len(v.p2 - v.p1); // 单位向量
p1 = q + n * k; p2 = q - n * k;
return 2; // 2个交点
}
};
template<typename T>
class Point {
public:
T x, y;
Point(T x = 0, T y = 0) : x(x), y(y) {}
// 向量长度
T len() {
return sqrt(len2());
}
// 向量长度的平方
T len2() {
return (*this) * (*this);
}
Point operator- (const Point& B) const { return Point(x - B.x, y - B.y); }
Point operator+ (const Point& B) const { return Point(x + B.x, y + B.y); }
T operator^ (const Point<T>& B) const { return x * B.y - y * B.x; } // 叉积
T operator* (const Point<T>& B) const { return x * B.x + y * B.y; } // 点积
Point operator* (const T& B) const { return Point(x * B, y * B); }
Point operator/ (const T& B) const { return Point(x / B, y / B); }
bool operator< (const Point& B) const { return x < B.x || (x == B.x && y < B.y); }
bool operator> (const Point& B) const { return x > B.x || (x == B.x && y > B.y); }
bool operator== (const Point& B) const { return Geo::sgn(x - B.x) == 0 && Geo::sgn(y - B.y) == 0; }
bool operator!= (const Point& B) const { return Geo::sgn(x - B.x) || Geo::sgn(y - B.y); }
friend ostream& operator<<(ostream& out, const Point& a) { out << '(' << a.x << ',' << a.y << ')'; return out; }
};
template<typename T>
class Line {
public:
Point<T> p1, p2; // 线上的两个点
Line() {}
Line(Point<T> p1, Point<T> p2) :p1(p1), p2(p2) {}
Line(Point<T> p, double angle) { // 根据一个点和倾斜角 angle 确定直线，0 <= angle < pi
p1 = p;
if (Geo::sgn(angle - Geo::PI / 2) == 0) { p2 = (p1 + Point<T>(0, 1)); }
else { p2 = (p1 + Point<T>(1, tan(angle))); }
}
Line(double a, double b, double c) { // ax + by + c = 0
if (Geo::sgn(a) == 0) {
p1 = Point<T>(0, -c / b);
p2 = Point<T>(1, -c / b);
}
else if (Geo::sgn(b) == 0) {
p1 = Point<T>(-c / a, 0);
p2 = Point<T>(-c / a, 1);
}
else {
p1 = Point<T>(0, -c / b);
p2 = Point<T>(1, (-c - a) / b);
}
}
friend ostream& operator<<(ostream& out, const Point<T>& a) { out << a.x << ',' << a.y; return out; }
};
template<typename T>
class Polygon : public vector<Point<T>> {
public:
Polygon(int n) :vector<Point<T>>(n) {};
friend ostream& operator<<(ostream& out, const Polygon<T>& a) {
for (auto& i : a)
out << i << ' ';
return out;
}
};
template<typename T>
class Circle {
public:
Point<T> c; // 圆心
T r; // 半径
Circle() {}
Circle(Point<T> c, T r) :c(c), r(r) {}
Circle(T x, T y, T _r) { c = Point<T>(x, y); r = _r; }
friend ostream& operator<<(ostream& out, const Circle<T>& a) {
out << a.c << ',' << a.r;
return out;
}
};
////////////////////////
}
namespace MT = MyTools;
using Math = MT::Math<ll>;
using mint = MT::ModInt<998244353>;
const int mod = 1e9 + 7;
const int N = 1e6 + 10;
void solve(int CASE)
{
int r, c; cin >> r >> c;
var a = vector<string>(r + 1);
fa(i, 1, r)cin >> a[i], a[i] = ' ' + a[i];
// 扩展域并查集
var s = vector<int>(2 * r + 1);
fa(i, 1, 2 * r)s[i] = i;
// 每列出现 1 的各个行
var g = vector<vector<int>>(c + 1);
fa(i, 1, r)
fa(j, 1, c)
if (a[i][j] == '1')
g[j].pb(i);
var find = [&](var find, int x)->int {
if (x != s[x])return s[x] = find(find, s[x]);
return s[x];
};
var merge = [&](int x, int y)->void {
s[find(find, y)] = find(find, x);
};
// 中心的怎么翻转都没用了
if (c % 2 == 1 and g[(c + 1) / 2].size() > 1) {
cout << 0 << endl;
return;
}
fa(i, 1, c / 2) { // 枚举列
var j = c - i + 1;
var tot = g[i].size() + g[j].size();
// 这列和对称列 1 的个数不能大于 2
if (tot > 2) {
cout << 0 << endl;
return;
}
if (tot <= 1)continue;
if (g[i].size() == 2) {
merge(g[i][0], g[i][1] + r);
merge(g[i][1], g[i][0] + r);
}
else if (g[j].size() == 2) {
merge(g[j][0], g[j][1] + r);
merge(g[j][1], g[j][0] + r);
}
else {
merge(g[i][0], g[j][0]);
merge(g[i][0] + r, g[j][0] + r);
}
}
fa(i, 1, r) {
if (s[find(find, i)] == s[find(find, i + n)]) {
cout << 0 << '\n';
return;
}
}
int ans = 0;
fa(i, 1, 2 * r)ans += (s[i] == i);
cout << Math::fastPow(2, ans / 2, mod) << endl;
return;
}
int main()
{
//SetConsoleOutputCP(CP_UTF8);
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int _ = 1;
cin >> _;
fa(i, 1, _)solve(i);
return 0;
}