Wojtek has just won a maths competition in Byteland! The prize is admirable — a great book called 'Card Tricks for Everyone.' 'Great!' he thought, 'I can finally use this old, dusted deck of cards that's always been lying unused on my desk!'

The first chapter of the book is 'How to Shuffle k Cards in Any Order You Want.' It's basically a list of n intricate methods of shuffling the deck of k cards in a deterministic way. Specifically, the i-th recipe can be described as a permutation (P_{i,1}, P_{i,2}, ..., P_{i,k}) of integers from 1 to k. If we enumerate the cards in the deck from 1 to k from top to bottom, then P_{i,j} indicates the number of the j-th card from the top of the deck after the shuffle.

The day is short and Wojtek wants to learn only some of the tricks today. He will pick two integers l, r (1 ≤ l ≤ r ≤ n), and he will memorize each trick from the l-th to the r-th, inclusive. He will then take a sorted deck of k cards and repeatedly apply random memorized tricks until he gets bored. He still likes maths, so he started wondering: how many different decks can he have after he stops shuffling it?

Wojtek still didn't choose the integers l and r, but he is still curious. Therefore, he defined f(l, r) as the number of different decks he can get if he memorizes all the tricks between the l-th and the r-th, inclusive. What is the value of

$$$∑_{l=1}^n ∑_{r=l}^n f(l, r)?$$$

Input

The first line contains two integers n, k (1 ≤ n ≤ 200 000, 1 ≤ k ≤ 5) — the number of tricks and the number of cards in Wojtek's deck.

Each of the following n lines describes a single trick and is described by k distinct integers P_{i,1}, P_{i,2}, ..., P_{i, k} (1 ≤ P_{i, j} ≤ k).

Output

Output the value of the sum described in the statement.

Examples

Input


3 3
2 1 3
3 1 2
1 3 2


Output


25


Input


2 4
4 1 3 2
4 3 1 2


Output


31

Note

Consider the first sample:

  * The first trick swaps two top cards. 
  * The second trick takes a card from the bottom and puts it on the top of the deck. 
  * The third trick swaps two bottom cards. 



The first or the third trick allow Wojtek to generate only two distinct decks (either the two cards are swapped or not). Therefore, f(1, 1) = f(3, 3) = 2.

The second trick allows him to shuffle the deck in a cyclic order. Therefore, f(2,2)=3.

It turns that two first tricks or two last tricks are enough to shuffle the deck in any way desired by Wojtek. Therefore, f(1,2) = f(2,3) = f(1,3) = 3! = 6.
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;
namespace {
const int MOD107 = 1000000007;
const int MOD998 = 998244353;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <class T>
using minheap = priority_queue<T, vector<T>, greater<T>>;
template <class T>
using maxheap = priority_queue<T, vector<T>, less<T>>;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct Modular {
 private:
  long long MODVALUE = 0;
  long long val = 0;
  Modular initModular(long long val) const { return Modular(val, MODVALUE); }
  inline void validate() const {}
  inline void validate(const Modular& other) const {}

 public:
  explicit operator long long() const { return val; }
  template <class T>
  Modular& operator=(const T& other) {
    val = (other % MODVALUE + MODVALUE) % MODVALUE;
    return *this;
  }
  template <class T>
  void setMod(const T& MOD) {
    MODVALUE = MOD;
  }
  Modular& operator+=(const Modular& other) {
    validate(other);
    val += other.val;
    if (val >= MODVALUE) val -= MODVALUE;
    return *this;
  }
  Modular operator+(const Modular& other) const {
    Modular tmp = *this;
    return tmp += other;
  }
  template <class T>
  Modular& operator+=(const T& other) {
    return *this += initModular(other);
  }
  template <class T>
  Modular operator+(const T& other) const {
    return *this + initModular(other);
  }
  template <class T>
  friend Modular operator+(const T& other, const Modular& m) {
    return m.initModular(other) + m;
  }
  Modular& operator++() { return *this += 1; }
  Modular operator++(int) {
    Modular tmp = *this;
    ++*this;
    return tmp;
  }
  Modular operator-() const { return initModular(-val); }
  Modular& operator-=(const Modular& other) {
    validate(other);
    val -= other.val;
    if (val < 0) val += MODVALUE;
    return *this;
  }
  Modular operator-(const Modular& other) const {
    Modular tmp = *this;
    return tmp -= other;
  }
  template <class T>
  Modular& operator-=(const T& other) {
    return *this -= initModular(other);
  }
  template <class T>
  Modular operator-(const T& other) const {
    return *this - initModular(other);
  }
  template <class T>
  friend Modular operator-(const T& other, const Modular& m) {
    return m.initModular(other) - m;
  }
  Modular& operator--() { return *this -= 1; }
  Modular operator--(int) {
    Modular tmp = *this;
    --*this;
    return tmp;
  }
  Modular& operator*=(const Modular& other) {
    validate(other);
    val *= other.val;
    val %= MODVALUE;
    if (val < 0) val += MODVALUE;
    return *this;
  }
  Modular operator*(const Modular& other) const {
    Modular tmp = *this;
    return tmp *= other;
  }
  template <class T>
  Modular& operator*=(const T& other) {
    return *this *= initModular(other);
  }
  template <class T>
  Modular operator*(const T& other) const {
    return *this * initModular(other);
  }
  template <class T>
  friend Modular operator*(const T& other, const Modular& m) {
    return m.initModular(other) * m;
  }
  Modular pow(long long power) const {
    Modular m = *this, ans = initModular(1);
    while (power) {
      if (power & 1) ans *= m;
      m *= m;
      power >>= 1;
    }
    return ans;
  }
  Modular pow(const Modular& other) const { return pow(other.val); }
  Modular inv() const { return pow(MODVALUE - 2); }
  Modular& operator/=(const Modular& other) {
    val *= other.inv().val;
    val %= MODVALUE;
    if (val < 0) val += MODVALUE;
    return *this;
  }
  Modular operator/(const Modular& other) const {
    Modular tmp = *this;
    return tmp /= other;
  }
  template <class T>
  Modular& operator/=(const T& other) {
    return *this /= initModular(other);
  }
  template <class T>
  Modular operator/(const T& other) const {
    return *this / initModular(other);
  }
  template <class T>
  friend Modular operator/(const T& other, const Modular& m) {
    return m.initModular(other) / m;
  }
  friend istream& operator>>(istream& in, Modular& m) {
    in >> m.val;
    m.val %= m.MODVALUE;
    if (m.val < 0) m.val += m.MODVALUE;
    return in;
  }
  friend ostream& operator<<(ostream& out, const Modular& m) {
    return out << m.val;
  }
  Modular() {
    val = 0;
    MODVALUE = 0;
  }
  Modular(long long val, long long MOD)
      : MODVALUE(MOD), val((val % MOD + MOD) % MOD) {}
};
using Mint = Modular;
inline ll binpow(ll b, ll p, ll mod) {
  b %= mod;
  ll ans = 1;
  for (; p > 0; p >>= 1) {
    if (p & 1) {
      ans *= b;
      ans %= mod;
    }
    b *= b;
    b %= mod;
  }
  return ans;
}
inline ll max(ll a, int b) { return (a > b ? a : b); }
inline ll max(int a, ll b) { return (a > b ? a : b); }
inline ll min(ll a, int b) { return (a < b ? a : b); }
inline ll min(int a, ll b) { return (a < b ? a : b); }
template <class T>
inline bool chkmin(T& x, const T& y) {
  return x > y ? x = y, 1 : 0;
}
template <class T>
inline bool chkmax(T& x, const T& y) {
  return x < y ? x = y, 1 : 0;
}
}  // namespace
namespace IO {
template <class T>
inline void _R(T& x) {
  cin >> x;
}
template <class T1, class T2>
inline void _R(pair<T1, T2>& x) {
  _R(x.first);
  _R(x.second);
}
template <class T>
inline void _R(vector<T>& x) {
  for (auto& i : x) _R(i);
}
template <class T>
inline void _R(deque<T>& x) {
  for (auto& i : x) _R(i);
}
inline void R() {}
template <class T1, class... T2>
inline void R(T1& x, T2&... y) {
  _R(x);
  R(y...);
}
template <class T>
inline void _W(const T& x);
template <class T1, class T2>
inline void _W(const pair<T1, T2>& p);
template <class... T>
inline void _W(const vector<T...>& x);
template <class... T>
inline void _W(const deque<T...>& x);
template <class... T>
inline void _W(const forward_list<T...>& x);
template <class... T>
inline void _W(const list<T...>& x);
template <class... T>
inline void _W(const set<T...>& x);
template <class... T>
inline void _W(const multiset<T...>& x);
template <class... T>
inline void _W(const unordered_set<T...>& x);
template <class... T>
inline void _W(const unordered_multiset<T...>& x);
template <class... T>
inline void _W(const map<T...>& x);
template <class... T>
inline void _W(const multimap<T...>& x);
template <class... T>
inline void _W(const unordered_map<T...>& x);
template <class... T>
inline void _W(const unordered_multimap<T...>& x);
template <class Container>
inline void printContainer(const Container& x) {
  bool isFirst = 1;
  for (auto i : x) {
    if (!isFirst) cout << ' ';
    isFirst = 0;
    _W(i);
  }
}
template <class T>
inline void _W(const T& x) {
  cout << x;
}
template <class T1, class T2>
inline void _W(const pair<T1, T2>& p) {
  _W(p.first);
  _W(' ');
  _W(p.second);
}
template <class... T>
inline void _W(const vector<T...>& x) {
  printContainer(x);
}
template <class... T>
inline void _W(const deque<T...>& x) {
  printContainer(x);
}
template <class... T>
inline void _W(const forward_list<T...>& x) {
  printContainer(x);
}
template <class... T>
inline void _W(const list<T...>& x) {
  printContainer(x);
}
template <class... T>
inline void _W(const set<T...>& x) {
  printContainer(x);
}
template <class... T>
inline void _W(const multiset<T...>& x) {
  printContainer(x);
}
template <class... T>
inline void _W(const unordered_set<T...>& x) {
  printContainer(x);
}
template <class... T>
inline void _W(const unordered_multiset<T...>& x) {
  printContainer(x);
}
template <class... T>
inline void _W(const map<T...>& x) {
  printContainer(x);
}
template <class... T>
inline void _W(const multimap<T...>& x) {
  printContainer(x);
}
template <class... T>
inline void _W(const unordered_map<T...>& x) {
  printContainer(x);
}
template <class... T>
inline void _W(const unordered_multimap<T...>& x) {
  printContainer(x);
}
inline void W() { cout << '\n'; }
template <class T>
inline void W(const T& x) {
  _W(x);
  W();
}
template <class T1, class... T2>
inline void W(const T1& x, const T2&... y) {
  _W(x);
  _W(' ');
  W(y...);
}
}  // namespace IO
using namespace IO;
namespace outputFormat {
inline string Case(int tc) { return "Case #" + to_string(tc) + ':'; }
inline string YN(bool b) { return b ? "Yes" : "No"; }
}  // namespace outputFormat
using namespace outputFormat;
namespace std {
template <class T1, class T2>
struct hash<pair<T1, T2>> {
  std::size_t operator()(pair<T1, T2> _) const {
    return hash<T1>{}(_.first) ^ hash<T2>{}(_.second);
  }
};
}  // namespace std
struct cmp {
  bool operator()(pii x, pii y) {
    if (x.second != y.second) return x.second > y.second;
    return x.first < y.first;
  }
};
int main() {
  int n, k;
  R(n, k);
  vector<int> fac(10, 1);
  for (int i = 2; i < 10; i++) fac[i] = fac[i - 1] * i;
  map<int, vector<int>> intToPerm;
  map<vector<int>, int> permToInt;
  {
    vector<int> perm(k);
    for (int i = 0; i < k; i++) perm[i] = i;
    for (int i = 0; i < fac[k]; i++) {
      intToPerm[i] = perm;
      permToInt[perm] = i;
      if (i + 1 < fac[k])
        assert(next_permutation((perm).begin(), (perm).end()));
    }
  }
  vector<vector<int>> compo(fac[k], vector<int>(fac[k], -1));
  for (int i = 0; i < fac[k]; i++) {
    vector<int> a = intToPerm[i];
    for (int j = 0; j < fac[k]; j++) {
      vector<int> b = intToPerm[j];
      vector<int> ans(k, -1);
      for (int l = 0; l < k; l++) ans[l] = a[b[l]];
      int ansv = permToInt[ans];
      compo[i][j] = ansv;
    }
  }
  ll ans = 0;
  vector<int> last(fac[k], -1);
  set<pii, cmp> s;
  for (int i = 0; i < fac[k]; i++) s.insert({i, last[i]});
  s.insert({INT_MAX, -1});
  for (int i = 0; i < n; i++) {
    vector<int> perm(k);
    R(perm);
    for (auto& x : perm) x--;
    int pv = permToInt[perm];
    s.erase({pv, last[pv]});
    assert((int)s.size() == fac[k]);
    last[pv] = i;
    s.insert({pv, last[pv]});
    vector<bool> group(fac[k], 0);
    vector<int> gen;
    int grpsz = 0;
    int last = i;
    for (auto& e : s) {
      int curpv = e.first;
      int pos = e.second;
      ans += grpsz * (last - pos);
      if (pos == -1) break;
      if (!group[curpv]) {
        group[curpv] = true;
        grpsz++;
        gen.emplace_back(curpv);
        queue<int> q;
        for (int j = 0; j < fac[k]; j++)
          if (group[j]) q.push(j);
        while (!q.empty()) {
          int now = q.front();
          q.pop();
          for (auto& g : gen) {
            int nxt = compo[g][now];
            int nxt2 = compo[now][g];
            if (!group[nxt]) {
              group[nxt] = true;
              grpsz++;
              q.push(nxt);
            }
            if (!group[nxt2]) {
              group[nxt2] = true;
              grpsz++;
              q.push(nxt2);
            }
          }
        }
      }
      last = pos;
    }
  }
  W(ans);
  return 0;
}
static auto __init__ = []() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout << fixed << setprecision(10);
  return 42;
}();
