Problem: A cubeword is a special type of a crossword. When building a cubeword, you start by choosing a positive integer a: the side length of the cube. Then, you build a big cube consisting of a × a × a unit cubes. This big cube has 12 edges. Then, you discard all unit cubes that do not touch the edges of the big cube. The figure below shows the object you will get for a=6.

<image>

Finally, you assign a letter to each of the unit cubes in the object. You must get a meaningful word along each edge of the big cube. Each edge can be read in either direction, and it is sufficient if one of the two directions of reading gives a meaningful word.

The figure below shows the object for a=6 in which some unit cubes already have assigned letters. You can already read the words 'SUBMIT', 'ACCEPT' and 'TURING' along three edges of the big cube.

<image>

You are given a list of valid words. Each word from the wordlist may appear on arbitrarily many edges of a valid cubeword. Find and report the number of different cubewords that can be constructed, modulo 998,244,353.

If one cubeword can be obtained from another by rotation or mirroring, they are considered distinct.

Input

The first line contains a single integer n (1 ≤ n ≤ 100,000) – the number of words.

Then, n lines follow. Each of these lines contains one word that can appear on the edges of the big cube. The length of each word is between 3 and 10, inclusive.

It is guaranteed that all words are different.

Output

Output a single integer, the number of distinct cubewords for the given list of valid words modulo 998,244,353.

Scoring

Subtask 1 (21 points): the words consist only of letters 'a' - 'f' (lowercase)

Subtask 2 (29 points): the words consist only of letters 'a' - 'p' (lowercase)

Subtask 3 (34 points): the words consist of letters 'a' - 'p' (lowercase) and 'A' - 'P' (uppercase)

Subtask 4 (16 points): the words consist of letters 'a' - 'z' (lowercase), 'A' - 'Z' (uppercase) and digits '0' - '9'

Examples

Input


1
radar


Output


1


Input


1
robot


Output


2


Input


2
FLOW
WOLF


Output


2


Input


2
baobab
bob


Output


4097


Input


3
TURING
SUBMIT
ACCEPT


Output


162


Input


3
MAN1LA
MAN6OS
AN4NAS


Output


114

Note

In the first sample, the only possibility is for the word "radar" to be on each edge of the cube.

In the second sample, there are two cubes, which are just rotations of each other – the word "robot" is on every edge, and the difference between the two cubes is whether the lower left front corner contains 'r' or 't'.

The third sample is similar to the second one. The fact that we can read the word on each edge in both directions does not affect the answer.

In the fourth sample, there is one cube with the word "bob" on each edge. There are also 2^{12} = 4096 cubes with the word "baobab" on each edge. (For each of the 12 edges, we have two possible directions in which the word "baobab" can appear.)

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize("Ofast")
#pragma GCC target( \
    "sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
inline int min(const int &first, const int &second) {
  return (((second - first) >> (32 - 1)) & (first ^ second)) ^ first;
}
inline int max(const int &first, const int &second) {
  return (((second - first) >> (32 - 1)) & (first ^ second)) ^ second;
}
inline long long min(const long long &first, const long long &second) {
  return (((second - first) >> (64 - 1)) & (first ^ second)) ^ first;
}
inline long long max(const long long &first, const long long &second) {
  return (((second - first) >> (64 - 1)) & (first ^ second)) ^ second;
}
using namespace std;
char string_in_buffer[(int)260];
void fast_scan(int &first) { scanf("%d", &first); }
void fast_scan(long long &first) { scanf("%lld", &first); }
void fast_scan(unsigned long long &first) { scanf("%llu", &first); }
void fast_scan(double &first) { scanf("%lf", &first); }
void fast_scan(long double &first) { scanf("%Lf", &first); }
void fast_scan(char &first) {
  scanf("%c", &first);
  if (first == '\n') {
    fast_scan(first);
  }
}
void fast_scan(string &first) {
  scanf("%s", string_in_buffer);
  first = string(string_in_buffer);
}
template <class TFirst, class TSecond>
void fast_scan(pair<TFirst, TSecond> &p) {
  fast_scan(p.first);
  fast_scan(p.second);
}
template <class T>
void fast_scan(vector<T> &v) {
  for (auto &first : v) fast_scan(first);
}
void fast_print(const int &first) { printf("%d", first); }
void fast_print(const unsigned int &first) { printf("%u", first); }
void fast_print(const long long &first) { printf("%lld", first); }
void fast_print(const unsigned long long &first) { printf("%llu", first); }
void fast_print(const double &first) { printf("%.15lf", first); }
void fast_print(const long double &first) { printf("%.15Lf", first); }
void fast_print(const char &first) { printf("%c", first); };
void fast_print(const string &first) { printf("%s", first.c_str()); }
void fast_print(const char v[]) { fast_print((string)v); }
template <class TFirst, class TSecond>
void fast_print(const pair<TFirst, TSecond> &p) {
  fast_print(p.first);
  fast_print(' ');
  fast_print(p.second);
}
template <class T>
void fast_print(const vector<T> &v) {
  if (v.empty()) return;
  fast_print(v[0]);
  for (int i = 1; i < v.size(); i++) {
    fast_print(' ');
    fast_print(v[i]);
  }
}
template <class T>
void fast_print(const vector<vector<T>> &v) {
  if (v.empty()) return;
  fast_print(v[0]);
  for (int i = 1; i < v.size(); i++) {
    fast_print('\n');
    fast_print(v[i]);
  }
}
template <class T>
void fast_print(const T &v) {
  for (const auto &first : v) {
    fast_print(first);
    fast_print(' ');
  }
}
using namespace std;
namespace smart_io {
string print_start = "";
string sep = " ";
bool first_print = false;
void precall_print() {
  fast_print(print_start);
  print_start = "\n";
  first_print = true;
}
void _print(deque<string>) {}
template <class T, class... Args>
void _print(deque<string> names, T elem, Args... args) {
  if (!first_print) {
    fast_print("\n");
  } else {
    first_print = false;
  }
  fast_print(names.front());
  fast_print(" = ");
  fast_print(elem);
  names.pop_front();
  _print(names, args...);
}
}  // namespace smart_io
template <class T>
ostream &operator,(ostream &os, const T &object) {
  if (!smart_io::first_print) {
    fast_print(smart_io::sep);
  } else {
    smart_io::first_print = false;
  }
  fast_print(object);
  return os;
}
template <class T>
istream &operator,(istream &is, T &object) {
  fast_scan(object);
  return is;
}
namespace escape__from__random__aetuhoetnuhshe {
using namespace std::chrono;
mt19937 rng(duration_cast<milliseconds>(system_clock::now().time_since_epoch())
                .count());
uniform_real_distribution<> prob_dist(0.0, 1.0);
};  // namespace escape__from__random__aetuhoetnuhshe
namespace typedefs {}
namespace numbers_operation {
template <class T>
T floor_mod(T a, T b) {
  if (a >= 0 && b >= 0) return a % b;
  if (a <= 0 && b <= 0) return a % b;
  return abs(b) - (abs(a) % abs(b));
}
}  // namespace numbers_operation
using namespace numbers_operation;
using namespace typedefs;
using namespace escape__from__random__aetuhoetnuhshe;
const long long MOD = 998244353;
template <long long MOD>
struct Ring {
  long long value = 0;
  Ring() {}
  Ring(int _value) {
    value = _value;
    value = floor_mod(value, MOD);
  }
  Ring(long long _value) {
    value = _value;
    value = floor_mod(value, MOD);
  }
  Ring pow(long long p) const {
    if (p == 0) return 1;
    if (p & 1) {
      return Ring(value).pow(p - 1) * value;
    } else {
      Ring sub = Ring(value).pow(p / 2);
      return sub * sub;
    }
  }
  Ring inv() const { return pow(MOD - 2); }
  void operator*=(const Ring<MOD> &b) {
    value *= b.value;
    value = floor_mod(value, MOD);
  }
  friend Ring operator*(Ring<MOD> a, const Ring<MOD> &b) {
    a *= b;
    return a;
  }
  void operator+=(const Ring<MOD> &b) {
    value += b.value;
    value = floor_mod(value, MOD);
  }
  friend Ring operator+(Ring a, const Ring &b) {
    a += b;
    return a;
  }
  void operator-=(const Ring<MOD> &b) {
    value -= b.value;
    value = floor_mod(value, MOD);
  }
  friend Ring operator-(Ring a, const Ring &b) {
    a -= b;
    return a;
  }
  void operator/=(const Ring<MOD> &b) { (*this) *= b.inv(); }
  friend Ring operator/(Ring a, const Ring &b) {
    a /= b;
    return a;
  }
  bool operator==(const Ring<MOD> &b) { return value == b.value; }
  bool operator!=(const Ring<MOD> &b) { return value != b.value; }
  friend void fast_print(const Ring<MOD> &b) { fast_print(b.value); }
};
int get_id(char c) {
  if ('a' <= c && c <= 'z') return c - 'a';
  if ('A' <= c && c <= 'Z') return c - 'A' + 26;
  return c - '0' + 52;
}
const int BAR = 62;
long long aosnetuhasonetuhas[62][62];
long long comp[62][62][62];
long long func[8] = {1, 4, 6, 12, 4, 12, 12, 24};
signed main(signed argc, char *argv[]) {
  int n;
  cin, n;
  vector<string> v(n);
  cin, v;
  vector<string> av;
  for (string s : v) {
    reverse(s.begin(), s.end());
    av.push_back(s);
  }
  v.insert(v.end(), av.begin(), av.end());
  sort(v.begin(), v.end());
  v.resize(unique(v.begin(), v.end()) - v.begin());
  long long M2 = MOD * MOD;
  long long gl = 0;
  for (int l = 3; l <= 10; l++) {
    memset(aosnetuhasonetuhas, 0, sizeof aosnetuhasonetuhas);
    for (string s : v) {
      if (((int)s.size()) != l) continue;
      string t = s;
      reverse(t.begin(), t.end());
      aosnetuhasonetuhas[get_id(s[0])][get_id(s.back())]++;
    }
    for (int a = 0; a < BAR; a++)
      for (int b = a; b < BAR; b++)
        for (int c = b; c < BAR; c++) {
          comp[a][b][c] = 0;
          for (int sub = 0; sub < (BAR); sub++)
            comp[a][b][c] += aosnetuhasonetuhas[a][sub] *
                             aosnetuhasonetuhas[b][sub] *
                             aosnetuhasonetuhas[c][sub];
          comp[a][b][c] %= MOD;
          comp[a][c][b] = comp[b][a][c] = comp[b][c][a] = comp[c][a][b] =
              comp[c][b][a] = comp[a][b][c];
        }
    for (int a = 0; a < BAR; a++)
      for (int b = a; b < BAR; b++)
        for (int c = b; c < BAR; c++)
          for (int d = c; d < BAR; d++) {
            int mask = ((b != a) | ((c != b) << 1) | ((d != c) << 2));
            gl += ((((((comp[a][b][c] * comp[b][c][d]) % MOD) * comp[c][d][a]) %
                     MOD) *
                    comp[d][a][b]) %
                   MOD) *
                  func[mask];
            gl -= M2 * (gl >= M2);
          }
  }
  smart_io::precall_print();
  cout, gl % MOD;
}