結果

問題 No.1397 Analog Graffiti
ユーザー LayCurseLayCurse
提出日時 2021-02-15 11:24:07
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 55 ms / 10,000 ms
コード長 22,918 bytes
コンパイル時間 3,070 ms
コンパイル使用メモリ 224,628 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-07-22 23:06:55
合計ジャッジ時間 4,652 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 3 ms
5,248 KB
testcase_01 AC 3 ms
5,376 KB
testcase_02 AC 55 ms
5,376 KB
testcase_03 AC 2 ms
5,376 KB
testcase_04 AC 3 ms
5,376 KB
testcase_05 AC 55 ms
5,376 KB
testcase_06 AC 2 ms
5,376 KB
testcase_07 AC 5 ms
5,376 KB
testcase_08 AC 5 ms
5,376 KB
testcase_09 AC 3 ms
5,376 KB
testcase_10 AC 2 ms
5,376 KB
testcase_11 AC 54 ms
5,376 KB
testcase_12 AC 10 ms
5,376 KB
testcase_13 AC 53 ms
5,376 KB
testcase_14 AC 53 ms
5,376 KB
testcase_15 AC 12 ms
5,376 KB
testcase_16 AC 10 ms
5,376 KB
testcase_17 AC 51 ms
5,376 KB
testcase_18 AC 52 ms
5,376 KB
testcase_19 AC 3 ms
5,376 KB
testcase_20 AC 2 ms
5,376 KB
testcase_21 AC 3 ms
5,376 KB
testcase_22 AC 24 ms
5,376 KB
testcase_23 AC 7 ms
5,376 KB
testcase_24 AC 3 ms
5,376 KB
testcase_25 AC 10 ms
5,376 KB
testcase_26 AC 3 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize ("Ofast")
#include<bits/stdc++.h>
using namespace std;
#define MD (998244353U)
template<class S, class T> inline S max_L(S a,T b){
  return a>=b?a:b;
}
struct Rand{
  unsigned x;
  unsigned y;
  unsigned z;
  unsigned w;
  Rand(void){
    x=123456789;
    y=362436069;
    z=521288629;
    w=(unsigned)time(NULL);
  }
  Rand(unsigned seed){
    x=123456789;
    y=362436069;
    z=521288629;
    w=seed;
  }
  inline unsigned get(void){
    unsigned t;
    t = (x^(x<<11));
    x=y;
    y=z;
    z=w;
    w = (w^(w>>19))^(t^(t>>8));
    return w;
  }
  inline double getUni(void){
    return get()/4294967296.0;
  }
  inline int get(int a){
    return (int)(a*getUni());
  }
  inline int get(int a, int b){
    return a+(int)((b-a+1)*getUni());
  }
  inline long long get(long long a){
    return(long long)(a*getUni());
  }
  inline long long get(long long a, long long b){
    return a+(long long)((b-a+1)*getUni());
  }
  inline double get(double a, double b){
    return a+(b-a)*getUni();
  }
  inline int getExp(int a){
    return(int)(exp(getUni()*log(a+1.0))-1.0);
  }
  inline int getExp(int a, int b){
    return a+(int)(exp(getUni()*log((b-a+1)+1.0))-1.0);
  }
}
;
struct Modint{
  unsigned val;
  Modint(){
    val=0;
  }
  Modint(int a){
    val = ord(a);
  }
  Modint(unsigned a){
    val = ord(a);
  }
  Modint(long long a){
    val = ord(a);
  }
  Modint(unsigned long long a){
    val = ord(a);
  }
  inline unsigned ord(unsigned a){
    return a%MD;
  }
  inline unsigned ord(int a){
    a %= (int)MD;
    if(a < 0){
      a += MD;
    }
    return a;
  }
  inline unsigned ord(unsigned long long a){
    return a%MD;
  }
  inline unsigned ord(long long a){
    a %= (int)MD;
    if(a < 0){
      a += MD;
    }
    return a;
  }
  inline unsigned get(){
    return val;
  }
  inline Modint &operator+=(Modint a){
    val += a.val;
    if(val >= MD){
      val -= MD;
    }
    return *this;
  }
  inline Modint &operator-=(Modint a){
    if(val < a.val){
      val = val + MD - a.val;
    }
    else{
      val -= a.val;
    }
    return *this;
  }
  inline Modint &operator*=(Modint a){
    val = ((unsigned long long)val*a.val)%MD;
    return *this;
  }
  inline Modint &operator/=(Modint a){
    return *this *= a.inverse();
  }
  inline Modint operator+(Modint a){
    return Modint(*this)+=a;
  }
  inline Modint operator-(Modint a){
    return Modint(*this)-=a;
  }
  inline Modint operator*(Modint a){
    return Modint(*this)*=a;
  }
  inline Modint operator/(Modint a){
    return Modint(*this)/=a;
  }
  inline Modint operator+(int a){
    return Modint(*this)+=Modint(a);
  }
  inline Modint operator-(int a){
    return Modint(*this)-=Modint(a);
  }
  inline Modint operator*(int a){
    return Modint(*this)*=Modint(a);
  }
  inline Modint operator/(int a){
    return Modint(*this)/=Modint(a);
  }
  inline Modint operator+(long long a){
    return Modint(*this)+=Modint(a);
  }
  inline Modint operator-(long long a){
    return Modint(*this)-=Modint(a);
  }
  inline Modint operator*(long long a){
    return Modint(*this)*=Modint(a);
  }
  inline Modint operator/(long long a){
    return Modint(*this)/=Modint(a);
  }
  inline Modint operator-(void){
    Modint res;
    if(val){
      res.val=MD-val;
    }
    else{
      res.val=0;
    }
    return res;
  }
  inline operator bool(void){
    return val!=0;
  }
  inline operator int(void){
    return get();
  }
  inline operator long long(void){
    return get();
  }
  inline Modint inverse(){
    int a = val;
    int b = MD;
    int u = 1;
    int v = 0;
    int t;
    Modint res;
    while(b){
      t = a / b;
      a -= t * b;
      swap(a, b);
      u -= t * v;
      swap(u, v);
    }
    if(u < 0){
      u += MD;
    }
    res.val = u;
    return res;
  }
  inline Modint pw(unsigned long long b){
    Modint a(*this);
    Modint res;
    res.val = 1;
    while(b){
      if(b&1){
        res *= a;
      }
      b >>= 1;
      a *= a;
    }
    return res;
  }
  inline bool operator==(int a){
    return ord(a)==val;
  }
  inline bool operator!=(int a){
    return ord(a)!=val;
  }
}
;
inline Modint operator+(int a, Modint b){
  return Modint(a)+=b;
}
inline Modint operator-(int a, Modint b){
  return Modint(a)-=b;
}
inline Modint operator*(int a, Modint b){
  return Modint(a)*=b;
}
inline Modint operator/(int a, Modint b){
  return Modint(a)/=b;
}
inline Modint operator+(long long a, Modint b){
  return Modint(a)+=b;
}
inline Modint operator-(long long a, Modint b){
  return Modint(a)-=b;
}
inline Modint operator*(long long a, Modint b){
  return Modint(a)*=b;
}
inline Modint operator/(long long a, Modint b){
  return Modint(a)/=b;
}
inline int my_getchar_unlocked(){
  static char buf[1048576];
  static int s = 1048576;
  static int e = 1048576;
  if(s == e && e == 1048576){
    e = fread_unlocked(buf, 1, 1048576, stdin);
    s = 0;
  }
  if(s == e){
    return EOF;
  }
  return buf[s++];
}
inline void rd(int &x){
  int k;
  int m=0;
  x=0;
  for(;;){
    k = my_getchar_unlocked();
    if(k=='-'){
      m=1;
      break;
    }
    if('0'<=k&&k<='9'){
      x=k-'0';
      break;
    }
  }
  for(;;){
    k = my_getchar_unlocked();
    if(k<'0'||k>'9'){
      break;
    }
    x=x*10+k-'0';
  }
  if(m){
    x=-x;
  }
}
struct MY_WRITER{
  char buf[1048576];
  int s;
  int e;
  MY_WRITER(){
    s = 0;
    e = 1048576;
  }
  ~MY_WRITER(){
    if(s){
      fwrite_unlocked(buf, 1, s, stdout);
    }
  }
}
;
MY_WRITER MY_WRITER_VAR;
void my_putchar_unlocked(int a){
  if(MY_WRITER_VAR.s == MY_WRITER_VAR.e){
    fwrite_unlocked(MY_WRITER_VAR.buf, 1, MY_WRITER_VAR.s, stdout);
    MY_WRITER_VAR.s = 0;
  }
  MY_WRITER_VAR.buf[MY_WRITER_VAR.s++] = a;
}
inline void wt_L(char a){
  my_putchar_unlocked(a);
}
inline void wt_L(int x){
  int s=0;
  int m=0;
  char f[10];
  if(x<0){
    m=1;
    x=-x;
  }
  while(x){
    f[s++]=x%10;
    x/=10;
  }
  if(!s){
    f[s++]=0;
  }
  if(m){
    my_putchar_unlocked('-');
  }
  while(s--){
    my_putchar_unlocked(f[s]+'0');
  }
}
inline void wt_L(Modint x){
  int i;
  i = (int)x;
  wt_L(i);
}
template<class T, class S, class U> inline void DigitF_L(T n, int sz, S res[], U b){
  int i;
  for(i=(0);i<(sz);i++){
    res[i] = n % b;
    n /= b;
  }
}
template<class T, class U> inline T GCD_L(T a, U b){
  T r;
  while(b){
    r=a;
    a=b;
    b=r%a;
  }
  return a;
}
#define ROLLING_HASH_MOD (2305843009213693951ULL)
#define ROLLING_HASH_PRIMITIVE_ROOT (3)
#define ROLLING_HASH_MAX_MEMORY (2000000)
int ROLLING_HASH_MEM;
unsigned long long ROLLING_HASH_BASE;
unsigned long long ROLLING_HASH_IBASE;
unsigned long long*ROLLING_HASH_PW = NULL;
unsigned long long*ROLLING_HASH_IPW = NULL;
inline unsigned long long rollingHash61_mul(unsigned long long a, unsigned long long b){
  __uint128_t r = (__uint128_t) a * b;
  a = (r >> 61) + (r & ROLLING_HASH_MOD);
  if(a >= ROLLING_HASH_MOD){
    a -= ROLLING_HASH_MOD;
  }
  return a;
}
inline unsigned long long rollingHash61_pow(unsigned long long a, unsigned long long b){
  unsigned long long r = 1;
  for(;;){
    if(b&1){
      r = rollingHash61_mul(r, a);
    }
    if(b==0){
      break;
    }
    b >>= 1;
    a = rollingHash61_mul(a, a);
  }
  return r;
}
void rollingHashInit(){
  int i;
  Rand rnd;
  unsigned long long x;
  for(i=(0);i<(20);i++){
    rnd.get(2);
  }
  do{
    x = rnd.get(1.0, (double)(ROLLING_HASH_MOD-2));
  }
  while(GCD_L(x, ROLLING_HASH_MOD-1)!= 1);
  ROLLING_HASH_BASE = rollingHash61_pow(ROLLING_HASH_PRIMITIVE_ROOT, x);
  ROLLING_HASH_IBASE = rollingHash61_pow(ROLLING_HASH_BASE, ROLLING_HASH_MOD - 2);
}
void rollingHash_expand(int k){
  int i;
  if(ROLLING_HASH_MEM >= k){
    return;
  }
  ROLLING_HASH_MEM =max_L(2 * ROLLING_HASH_MEM, k);
  assert(ROLLING_HASH_MEM <= 2 * ROLLING_HASH_MAX_MEMORY);
  ROLLING_HASH_PW = (unsigned long long*) realloc(ROLLING_HASH_PW, ROLLING_HASH_MEM * sizeof(unsigned long long));
  ROLLING_HASH_IPW = (unsigned long long*) realloc(ROLLING_HASH_IPW, ROLLING_HASH_MEM * sizeof(unsigned long long));
  ROLLING_HASH_PW[0] = 1;
  for(i=(1);i<(ROLLING_HASH_MEM);i++){
    ROLLING_HASH_PW[i] = rollingHash61_mul(ROLLING_HASH_PW[i-1], ROLLING_HASH_BASE);
  }
  ROLLING_HASH_IPW[0] = 1;
  for(i=(1);i<(ROLLING_HASH_MEM);i++){
    ROLLING_HASH_IPW[i] = rollingHash61_mul(ROLLING_HASH_IPW[i-1], ROLLING_HASH_IBASE);
  }
}
struct rollingHash{
  long long len;
  unsigned long long hs;
  template<class T> void set(int N, T A[]){
    int i;
    long long tmp;
    hs = 0;
    len = N;
    rollingHash_expand(N);
    for(i=(0);i<(N);i++){
      tmp = A[i] % ((long long)ROLLING_HASH_MOD);
      if(tmp < 0){
        tmp += ROLLING_HASH_MOD;
      }
      hs += rollingHash61_mul(tmp, ROLLING_HASH_PW[i]);
      if(hs >= ROLLING_HASH_MOD){
        hs -= ROLLING_HASH_MOD;
      }
    }
  }
  template<class S, class T> void change(long long ind, S bef, T aft){
    long long tmp1;
    long long tmp2;
    tmp1 = bef % ((long long)ROLLING_HASH_MOD);
    tmp2 = aft % ((long long)ROLLING_HASH_MOD);
    tmp1 = tmp2 - tmp1;
    if(tmp1 < 0){
      tmp1 += ROLLING_HASH_MOD;
    }
    if(tmp1 < 0){
      tmp1 += ROLLING_HASH_MOD;
    }
    if(tmp1 >= ROLLING_HASH_MOD){
      tmp1 -= ROLLING_HASH_MOD;
    }
    if(ind+1 <= ROLLING_HASH_MAX_MEMORY || ind+1 >= ROLLING_HASH_MEM){
      rollingHash_expand(ind+1);
      hs += rollingHash61_mul(tmp1, ROLLING_HASH_PW[ind]);
    }
    else{
      hs += rollingHash61_mul(tmp1, rollingHash61_pow(ROLLING_HASH_BASE, ind));
    }
    if(hs >= ROLLING_HASH_MOD){
      hs -= ROLLING_HASH_MOD;
    }
  }
  void push_front(rollingHash a){
    if(a.len + 1 <= ROLLING_HASH_MAX_MEMORY || a.len + 1 >= ROLLING_HASH_MEM){
      rollingHash_expand(a.len + 1);
      hs = rollingHash61_mul(hs, ROLLING_HASH_PW[a.len]);
    }
    else{
      hs = rollingHash61_mul(hs, rollingHash61_pow(ROLLING_HASH_BASE, a.len));
    }
    hs += a.hs;
    if(hs >= ROLLING_HASH_MOD){
      hs -= ROLLING_HASH_MOD;
    }
    len += a.len;
  }
  void push_back(rollingHash a){
    if(len + 1 <= ROLLING_HASH_MAX_MEMORY || len + 1 >= ROLLING_HASH_MEM){
      rollingHash_expand(len + 1);
      hs += rollingHash61_mul(a.hs, ROLLING_HASH_PW[len]);
    }
    else{
      hs += rollingHash61_mul(a.hs, rollingHash61_pow(ROLLING_HASH_BASE, len));
    }
    if(hs >= ROLLING_HASH_MOD){
      hs -= ROLLING_HASH_MOD;
    }
    len += a.len;
  }
  void pop_front(rollingHash a){
    if(hs >= a.hs){
      hs -= a.hs;
    }
    else{
      hs = hs + ROLLING_HASH_MOD - a.hs;
    }
    if(a.len + 1 <= ROLLING_HASH_MAX_MEMORY || a.len + 1 >= ROLLING_HASH_MEM){
      rollingHash_expand(a.len + 1);
      hs = rollingHash61_mul(hs, ROLLING_HASH_IPW[a.len]);
    }
    else{
      hs = rollingHash61_mul(hs, rollingHash61_pow(ROLLING_HASH_IBASE, a.len));
    }
    len -= a.len;
  }
  void pop_back(rollingHash a){
    unsigned long long tmp;
    if(len + 1 <= ROLLING_HASH_MAX_MEMORY || len + 1 >= ROLLING_HASH_MEM){
      rollingHash_expand(len + 1);
      tmp = rollingHash61_mul(a.hs, ROLLING_HASH_PW[len]);
    }
    else{
      tmp = rollingHash61_mul(a.hs, rollingHash61_pow(ROLLING_HASH_BASE, len));
    }
    if(hs >= tmp){
      hs -= tmp;
    }
    else{
      hs = hs + ROLLING_HASH_MOD - tmp;
    }
    len -= a.len;
  }
  bool operator==(const rollingHash a){
    return len == a.len && hs == a.hs;
  }
  bool operator!=(const rollingHash a){
    return len != a.len || hs != a.hs;
  }
}
;
template<class T> rollingHash calcRollingHash(int N, T A[]){
  rollingHash res;
  res.set(N, A);
  return res;
}
struct rollingHashSubarrays{
  unsigned long long*hs;
  int mem;
  int len;
  void set(){
    hs = NULL;
    mem = len = 0;
  }
  void free(){
    if(mem){
      delete[] hs;
    }
  }
  void expand(int k){
    if(mem >= k){
      return;
    }
    free();
    mem =max_L(2*mem, k);
    hs = new unsigned long long[mem];
  }
  template<class T> void set(int N, T A[]){
    int i;
    long long tmp;
    if(N <= 0){
      return;
    }
    rollingHash_expand(N);
    expand(N);
    len = N;
    tmp = A[0] % ((long long)ROLLING_HASH_MOD);
    if(tmp < 0){
      tmp += ROLLING_HASH_MOD;
    }
    hs[0] = tmp;
    for(i=(1);i<(N);i++){
      tmp = A[i] % ((long long)ROLLING_HASH_MOD);
      if(tmp < 0){
        tmp += ROLLING_HASH_MOD;
      }
      hs[i] = hs[i-1] + rollingHash61_mul(tmp, ROLLING_HASH_PW[i]);
      if(hs[i] >= ROLLING_HASH_MOD){
        hs[i] -= ROLLING_HASH_MOD;
      }
    }
  }
  rollingHash get_len(int s, int len){
    unsigned long long x;
    rollingHash res;
    res.len = len;
    rollingHash_expand(s+1);
    if(s == 0){
      res.hs = hs[len-1];
    }
    else{
      if(hs[s+len-1] >= hs[s-1]){
        res.hs = hs[s+len-1] - hs[s-1];
      }
      else{
        res.hs = hs[s+len-1] + ROLLING_HASH_MOD - hs[s-1];
      }
      res.hs = rollingHash61_mul(res.hs, ROLLING_HASH_IPW[s]);
    }
    return res;
  }
  rollingHash get(int a, int b){
    return get_len(a, b - a + 1);
  }
  rollingHashSubarrays(){
    set();
  }
  ~rollingHashSubarrays(){
    free();
  }
}
;
unsigned long long HashMap_ullP_L[4];
template<class KEY, class VAL> struct HashMap{
  char*used;
  KEY*key;
  VAL*val;
  int mem;
  int n;
  int mask;
  HashMap(){
    mem = 0;
  }
  ~HashMap(){
    free();
  }
  void expand(int nn){
    if(mem >= nn){
      return;
    }
    if(mem){
      free();
    }
    mem = nn;
    used = new char[nn];
    key = new KEY[nn];
    val = new VAL[nn];
  }
  void free(){
    if(mem){
      mem = 0;
      delete[] used;
      delete[] key;
      delete[] val;
    }
  }
  void init(int nn){
    int i;
    n = 1;
    nn = nn + (nn + 1) / 2;
    while(n < nn){
      n *= 2;
    }
    mask = n - 1;
    expand(n);
    for(i=(0);i<(n);i++){
      used[i] = 0;
    }
  }
  inline int getHash(const int a){
    unsigned long long d = a;
    d = (((d * HashMap_ullP_L[0]) >> 32) * HashMap_ullP_L[1]) & mask;
    return d;
  }
  inline int getHash(const unsigned a){
    unsigned long long d = a;
    d = (((d * HashMap_ullP_L[0]) >> 32) * HashMap_ullP_L[1]) & mask;
    return d;
  }
  inline int getHash(const long long a){
    unsigned long long d = a;
    d = (((((d * HashMap_ullP_L[0]) >> 32) * HashMap_ullP_L[1]) >> 32) * HashMap_ullP_L[2]) & mask;
    return d;
  }
  inline int getHash(const unsigned long long a){
    unsigned long long d = a;
    d = (((((d * HashMap_ullP_L[0]) >> 32) * HashMap_ullP_L[1]) >> 32) * HashMap_ullP_L[2]) & mask;
    return d;
  }
  inline int getHash(const pair<int,int> a){
    unsigned long long d = (((unsigned long long)a.first) << 32) + ((unsigned long long)a.second);
    d = (((((d * HashMap_ullP_L[0]) >> 32) * HashMap_ullP_L[1]) >> 32) * HashMap_ullP_L[2]) & mask;
    return d;
  }
  inline VAL& operator[](const KEY a){
    int k = getHash(a);
    for(;;){
      if(used[k]==1 && key[k]==a){
        break;
      }
      if(used[k]==0){
        used[k] = 1;
        key[k] = a;
        break;
      }
      k = (k+1) & mask;
    }
    return val[k];
  }
  inline bool exist(const KEY a){
    int k = getHash(a);
    for(;;){
      if(used[k]==1 && key[k]==a){
        return true;
      }
      if(used[k]==0){
        break;
      }
      k = (k+1) & mask;
    }
    return false;
  }
  template<class S> inline bool exist(const KEY a, S &res){
    int k = getHash(a);
    for(;;){
      if(used[k]==1 && key[k]==a){
        res = val[k];
        return true;
      }
      if(used[k]==0){
        break;
      }
      k = (k+1) & mask;
    }
    return false;
  }
}
;
int X;
int Y;
int N;
HashMap<unsigned long long,int> hs;
int node;
int st[200][6];
int edge[200][200];
Modint dp[57][200];
Modint dn[57][200];
int get_node(int arr[]){
  int i;
  unsigned long long s;
  s = calcRollingHash(Y, arr).hs;
  if(hs.exist(s)){
    return hs[s];
  }
  hs[s] = node;
  for(i=(0);i<(Y);i++){
    st[node][i] = arr[i];
  }
  return node++;
}
void do_ord(int arr[]){
  int i;
  int k = 0;
  int f;
  for(i=(0);i<(Y);i++){
    if(arr[i]){
      arr[i] += 1000;
    }
  }
  for(i=(0);i<(Y);i++){
    if(arr[i] >= 1000){
      int j;
      k++;
      f = arr[i];
      for(j=(0);j<(Y);j++){
        if(arr[j] == f){
          arr[j] = k;
        }
      }
    }
  }
}
void chg(int arr[], int f, int t){
  int i;
  for(i=(0);i<(Y);i++){
    if(arr[i]==f){
      arr[i] = t;
    }
  }
}
int main(){
  int n;
  {
    rollingHashInit();
  }
  {
    int i;
    int j;
    int k;
    Rand rnd;
    for(i=(0);i<(20);i++){
      rnd.get(2);
    }
    for(i=(0);i<(4);i++){
      for(j=(0);j<(32);j++){
        k = rnd.get(1,62);
        HashMap_ullP_L[i] |= (1ULL << k);
      }
      HashMap_ullP_L[i] |= (1ULL << 0);
      HashMap_ullP_L[i] |= (1ULL << 63);
    }
  }
  int x;
  int y;
  int z;
  int cost;
  int arr[6] = {};
  int tp[6];
  int nx[6];
  Modint res = 0;
  rd(X);
  rd(Y);
  rd(N);
  if(N%2){
    wt_L(0);
    wt_L('\n');
    return 0;
  }
  N /= 2;
  hs.init(200);
  get_node(arr);
  for(n=(0);n<(node);n++){
    int i, mask;
    for(i=(0);i<(Y);i++){
      arr[i] = st[n][i];
    }
    for(mask=(0);mask<(1<<Y);mask++){
      DigitF_L(mask, Y, nx, 2);
      int APIVbQlN;
      int YREPHmFM;
      if(Y==0){
        YREPHmFM = 0;
      }
      else{
        YREPHmFM = arr[0];
        for(APIVbQlN=(1);APIVbQlN<(Y);APIVbQlN++){
          YREPHmFM = max_L(YREPHmFM, arr[APIVbQlN]);
        }
      }
      if(mask == 0 &&YREPHmFM!= 1){
        continue;
      }
      for(i=(0);i<(Y-1);i++){
        if(arr[i] != 0 && arr[i] != arr[i+1]){
          int j;
          for(j=(i+1);j<(Y);j++){
            if(arr[i] == arr[j]){
              int jPV_0s1p;
              remove_reference<decltype(nx[jPV_0s1p])>::type BUotOFBp;
              int Q5rsz4fz = 0;
              if((i) > ((j+1)-1)){
                BUotOFBp = 0;
              }
              else{
                for(jPV_0s1p = i; jPV_0s1p <= (j+1)-1; jPV_0s1p++){
                  if(Q5rsz4fz == 0){
                    BUotOFBp = nx[jPV_0s1p];
                    Q5rsz4fz = 1;
                    continue;
                  }
                  BUotOFBp += nx[jPV_0s1p];
                }
              }
              if(BUotOFBp== (j-i+1)){
                goto hCmBdyQB;
              }
            }
          }
        }
      }
      for(i=(0);i<(Y);i++){
        tp[i] = arr[i];
      }
      for(i=(0);i<(Y);i++){
        if(nx[i]){
          nx[i] = Y + i;
        }
      }
      for(i=(0);i<(Y);i++){
        if(tp[i] && nx[i]){
          {
            auto H31bcJ8S = (tp[i]);
            auto dtiCQK_a = ( nx[i]);
            x = H31bcJ8S;
            y = dtiCQK_a;
          }
          chg(tp, x, y);
          chg(nx, x, y);
        }
      }
      for(i=(1);i<(Y);i++){
        if(nx[i] && nx[i-1]){
          {
            auto lQU550vz = (nx[i]);
            auto qE8LMwYZ = ( nx[i-1]);
            x = lQU550vz;
            y = qE8LMwYZ;
          }
          chg(tp, x, y);
          chg(nx, x, y);
        }
      }
      for(i=(0);i<(Y);i++){
        if(mask && tp[i]){
          int j;
          for(j=(0);j<(Y);j++){
            if(tp[i] == nx[j]){
              goto dKuENJNI;
            }
          }
          goto hCmBdyQB;
        }
        dKuENJNI:;
      }
      do_ord(nx);
      z = get_node(nx);
      cost = 0;
      for(i=(0);i<(Y+1);i++){
        x = y = 0;
        if(i-1 >= 0 && arr[i-1]){
          x++;
          y |= 1;
        }
        if(i-1 >= 0 && nx[i-1]){
          x++;
          y |= 2;
        }
        if(i < Y && arr[i]){
          x++;
          y |= 4;
        }
        if(i < Y && nx[i]){
          x++;
          y |= 8;
        }
        if(y == 9 || y == 6){
          goto hCmBdyQB;
        }
        cost += x % 2;
      }
      edge[n][z] = 1 + cost / 2;
      hCmBdyQB:;
    }
  }
  dp[0][0] = 1;
  for(n=(0);n<(X+1);n++){
    int i;
    for(i=(0);i<(N+1);i++){
      int j;
      for(j=(0);j<(node);j++){
        dn[i][j] = 0;
      }
    }
    for(i=(0);i<(N+1);i++){
      int j;
      for(j=(0);j<(node);j++){
        int k;
        for(k=(0);k<(node);k++){
          if(edge[j][k]){
            if(i + edge[j][k] - 1 <= N){
              dn[i+edge[j][k]-1][k] += dp[i][j];
            }
          }
        }
      }
    }
    for(i=(0);i<(N+1);i++){
      int j;
      for(j=(0);j<(node);j++){
        dp[i][j] = dn[i][j];
      }
    }
    res += dp[N][0] * (X - n + 1);
    for(i=(0);i<(N+1);i++){
      dp[i][0] = 0;
    }
  }
  wt_L(res);
  wt_L('\n');
  return 0;
}
// cLay version 20210103-1 [bug fixed 2]

// --- original code ---
// #define MD 998244353
// int X, Y, N;
// 
// HashMap<ull,int> hs;
// int node, st[200][6];
// int edge[200][200];
// Modint dp[57][200], dn[57][200];
// 
// int get_node(int arr[]){
//   ull s;
//   s = calcRollingHash(Y, arr).hs;
//   if(hs.exist(s)) return hs[s];
//   hs[s] = node;
//   rep(i,Y) st[node][i] = arr[i];
//   return node++;
// }
// 
// void do_ord(int arr[]){
//   int k = 0, f;
//   rep(i,Y) if(arr[i]) arr[i] += 1000;
//   rep(i,Y) if(arr[i] >= 1000){
//     k++;
//     f = arr[i];
//     rep(j,Y) if(arr[j] == f) arr[j] = k;
//   }
// }
// 
// void chg(int arr[], int f, int t){
//   rep(i,Y) if(arr[i]==f) arr[i] = t;
// }
// 
// {
//   int x, y, z, cost;
//   int arr[6] = {}, tp[6], nx[6];
//   Modint res = 0;
//   rd(X,Y,N);
//   if(N%2) wt(0), return 0;
//   N /= 2;
// 
//   hs.init(200);
// 
//   get_node(arr);
//   rep(n,node){
//     rep(i,Y) arr[i] = st[n][i];
//     rep(mask,1<<Y){
//       DigitF(mask, Y, nx, 2);
//       if(mask == 0 && max(arr(Y)) != 1) continue;
//       rep(i,Y-1) if(arr[i] != 0 && arr[i] != arr[i+1]) rep(j,i+1,Y) if(arr[i] == arr[j]){
//         if(sum[k,i,j+1](nx[k]) == (j-i+1)) break_break_continue;
//       }
//       rep(i,Y) tp[i] = arr[i];
//       rep(i,Y) if(nx[i]) nx[i] = Y + i;
//       rep(i,Y) if(tp[i] && nx[i]){
//         (x, y) = (tp[i], nx[i]);
//         chg(tp, x, y); chg(nx, x, y);
//       }
//       rep(i,1,Y) if(nx[i] && nx[i-1]){
//         (x, y) = (nx[i], nx[i-1]);
//         chg(tp, x, y); chg(nx, x, y);
//       }
//       rep(i,Y) if(mask && tp[i]){
//         rep(j,Y) if(tp[i] == nx[j]) break_continue;
//         break_continue;
//       }
//       do_ord(nx);
//       z = get_node(nx);
//       cost = 0;
//       rep(i,Y+1){
//         x = y = 0;
//         if(i-1 >= 0 && arr[i-1]) x++, y |= 1;
//         if(i-1 >= 0 && nx[i-1]) x++, y |= 2;
//         if(i < Y && arr[i]) x++, y |= 4;
//         if(i < Y && nx[i]) x++, y |= 8;
//         if(y == 9 || y == 6) break_continue;
//         cost += x % 2;
//       }
//       edge[n][z] = 1 + cost / 2;
//     }
//   }
// 
//   dp[0][0] = 1;
//   rep(n,X+1){
//     rep(i,N+1) rep(j,node) dn[i][j] = 0;
//     rep(i,N+1) rep(j,node) rep(k,node) if(edge[j][k]){
//       if(i + edge[j][k] - 1 <= N) dn[i+edge[j][k]-1][k] += dp[i][j];
//     }
//     rep(i,N+1) rep(j,node) dp[i][j] = dn[i][j];
//     res += dp[N][0] * (X - n + 1);
//     rep(i,N+1) dp[i][0] = 0;
//   }
// 
//   wt(res);
// }
0