1395_E. Boboniu Walks on Graph_36677
Boboniu has a directed graph with n vertices and m edges.

The out-degree of each vertex is at most k.

Each edge has an integer weight between 1 and m. No two edges have equal weights.

Boboniu likes to walk on the graph with some specific rules, which is represented by a tuple (c_1,c_2,…,c_k). If he now stands on a vertex u with out-degree i, then he will go to the next vertex by the edge with the c_i-th (1≤ c_i≤ i) smallest weight among all edges outgoing from u.

Now Boboniu asks you to calculate the number of tuples (c_1,c_2,…,c_k) such that

  * 1≤ c_i≤ i for all i (1≤ i≤ k). 
  * Starting from any vertex u, it is possible to go back to u in finite time by walking on the graph under the described rules. 

Input

The first line contains three integers n, m and k (2≤ n≤ 2⋅ 10^5, 2≤ m≤ min(2⋅ 10^5,n(n-1) ), 1≤ k≤ 9).

Each of the next m lines contains three integers u, v and w (1≤ u,v≤ n,u≠ v,1≤ w≤ m), denoting an edge from u to v with weight w. It is guaranteed that there are no self-loops or multiple edges and each vertex has at least one edge starting from itself.

It is guaranteed that the out-degree of each vertex is at most k and no two edges have equal weight.

Output

Print one integer: the number of tuples.

Examples

Input


4 6 3
4 2 1
1 2 2
2 4 3
4 1 4
4 3 5
3 1 6


Output


2


Input


5 5 1
1 4 1
5 1 2
2 5 3
4 3 4
3 2 5


Output


1


Input


6 13 4
3 5 1
2 5 2
6 3 3
1 4 4
2 6 5
5 3 6
4 1 7
4 3 8
5 2 9
4 2 10
2 1 11
6 1 12
4 6 13


Output


1

Note

For the first example, there are two tuples: (1,1,3) and (1,2,3). The blue edges in the picture denote the c_i-th smallest edges for each vertex, which Boboniu chooses to go through.

<image>

For the third example, there's only one tuple: (1,2,2,2).

<image>

The out-degree of vertex u means the number of edges outgoing from u.
#include <bits/stdc++.h>
using namespace std;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
template <class T>
void IN(T& x) {
  cin >> x;
}
template <class H, class... T>
void IN(H& h, T&... t) {
  IN(h);
  IN(t...);
}
template <class T1, class T2>
void OUT(const pair<T1, T2>& x);
template <class T>
void OUT(const T& x) {
  cout << x;
}
template <class H, class... T>
void OUT(const H& h, const T&... t) {
  OUT(h);
  OUT(t...);
}
template <class T1, class T2>
void OUT(const pair<T1, T2>& x) {
  OUT(x.first, ' ', x.second);
}
template <class... T>
void OUTL(const T&... t) {
  OUT(t..., "\n");
}
template <class H>
void OUTLS(const H& h) {
  OUTL(h);
}
template <class H, class... T>
void OUTLS(const H& h, const T&... t) {
  OUT(h, ' ');
  OUTLS(t...);
}
void program();
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  program();
}
const int MX = 5e5;
int n, m, k;
vector<pair<int, int> > adj[MX];
long long h[MX];
long long f[10][10];
long long tot;
int getAns(int i, long long bm) {
  if (i == k) {
    if (bm == tot) return 1;
    return 0;
  }
  int ans = 0;
  for (int j = int(0); j < int(i + 1); j++) {
    bm ^= f[i][j];
    ans += getAns(i + 1, bm);
    bm ^= f[i][j];
  }
  return ans;
}
void program() {
  IN(n, m, k);
  for (int i = int(0); i < int(m); i++) {
    int u, v, w;
    IN(u, v, w);
    u--;
    v--;
    adj[u].push_back({w, v});
  }
  for (int i = int(0); i < int(n); i++) sort(adj[i].begin(), adj[i].end());
  for (int i = int(0); i < int(n); i++) h[i] = rng();
  for (int i = int(0); i < int(10); i++)
    for (int j = int(0); j < int(10); j++) f[i][j] = 0;
  for (int u = int(0); u < int(n); u++) {
    for (int i = int(0); i < int(adj[u].size()); i++) {
      f[adj[u].size() - 1][i] ^= h[adj[u][i].second];
    }
  }
  tot = 0;
  for (int i = int(0); i < int(n); i++) tot ^= h[i];
  OUTL(getAns(0, 0));
}

4 6 3
4 2 1
1 2 2
2 4 3
4 1 4
4 3 5
3 1 6
 5 5 1
1 4 1
5 1 2
2 5 3
4 3 4
3 2 5
 6 13 4
3 5 1
2 5 2
6 3 3
1 4 4
2 6 5
5 3 6
4 1 7
4 3 8
5 2 9
4 2 10
2 1 11
6 1 12
4 6 13
 6 12 4
1 4 1
4 5 2
6 1 3
5 1 4
6 4 5
1 3 6
6 5 7
4 2 8
1 5 9
2 1 10
3 6 11
6 2 12
 9 60 9
8 4 1
2 6 2
4 3 3
2 9 4
6 7 5
7 6 6
7 8 7
9 5 8
2 8 9
1 8 10
2 7 11
2 4 12
6 1 13
9 2 14
4 9 15
3 7 16
4 7 17
7 4 18
8 7 19
5 1 20
8 3 21
4 5 22
5 9 23
9 6 24
7 5 25
9 4 26
6 9 27
2 5 28
8 6 29
1 7 30
1 3 31
8 2 32
3 5 33
4 8 34
3 4 35
5 2 36
8 5 37
6 3 38
7 2 39
7 1 40
9 7 41
5 8 42
4 1 43
8 1 44
9 3 45
4 2 46
6 2 47
6 5 48
6 8 49
1 9 50
5 6 51
5 3 52
7 3 53
5 4 54
1 2 55
8 9 56
4 6 57
2 3 58
5 7 59
6 4 60
 6 24 5
4 6 1
2 4 2
3 4 3
6 2 4
5 3 5
4 3 6
4 2 7
4 5 8
6 4 9
1 3 10
5 6 11
3 2 12
5 2 13
3 1 14
5 1 15
1 5 16
1 4 17
5 4 18
1 6 19
3 5 20
2 6 21
1 2 22
2 1 23
3 6 24
 4 4 1
2 1 1
4 1 2
3 2 3
1 2 4
 2 2 1
2 1 1
1 2 2
 7 35 6
1 5 1
5 3 2
2 7 3
4 3 4
7 1 5
2 5 6
1 3 7
7 4 8
1 4 9
1 2 10
4 1 11
5 7 12
7 3 13
6 5 14
6 4 15
3 5 16
5 1 17
6 1 18
4 7 19
2 3 20
2 4 21
3 2 22
2 6 23
1 7 24
4 5 25
1 6 26
6 7 27
6 2 28
5 4 29
6 3 30
5 6 31
4 2 32
5 2 33
7 2 34
3 7 35
 3 3 1
2 3 1
1 2 2
3 1 3
 7 28 5
2 7 1
4 2 2
7 5 3
3 5 4
6 3 5
5 3 6
7 4 7
1 6 8
3 6 9
2 6 10
4 3 11
1 7 12
1 3 13
5 7 14
2 4 15
7 3 16
5 1 17
3 2 18
5 6 19
4 7 20
6 4 21
1 2 22
2 3 23
1 5 24
4 1 25
7 6 26
7 2 27
6 2 28
 7 13 2
6 5 1
3 6 2
2 3 3
4 1 4
4 6 5
5 3 6
7 3 7
1 2 8
2 4 9
7 4 10
3 2 11
6 1 12
5 7 13
 10 44 8
7 4 1
6 5 2
6 3 3
8 6 4
9 8 5
6 2 6
8 1 7
1 6 8
2 1 9
1 5 10
2 3 11
1 3 12
1 4 13
10 1 14
5 4 15
5 2 16
1 10 17
9 1 18
5 7 19
8 10 20
4 9 21
6 9 22
6 8 23
6 10 24
1 9 25
8 4 26
6 7 27
2 5 28
3 6 29
4 2 30
10 6 31
8 3 32
5 9 33
4 3 34
3 9 35
7 6 36
3 10 37
10 2 38
7 3 39
9 10 40
2 10 41
6 1 42
9 3 43
10 3 44
 6 9 2
3 1 1
2 5 2
1 6 3
6 2 4
5 4 5
5 1 6
1 4 7
4 3 8
4 1 9
 7 17 4
3 6 1
5 7 2
2 5 3
1 7 4
4 5 5
6 4 6
7 3 7
3 1 8
6 1 9
4 6 10
1 5 11
6 7 12
1 2 13
7 2 14
2 4 15
5 3 16
6 5 17
 10 50 8
7 6 1
7 3 2
7 10 3
7 1 4
7 2 5
6 3 6
6 10 7
6 1 8
6 2 9
6 8 10
3 10 11
3 1 12
3 2 13
3 8 14
3 5 15
10 1 16
10 2 17
10 8 18
10 5 19
10 9 20
1 2 21
1 8 22
1 5 23
1 9 24
1 4 25
2 8 26
2 5 27
2 9 28
2 4 29
2 7 30
8 5 31
8 9 32
8 4 33
8 7 34
8 6 35
5 9 36
5 4 37
5 7 38
5 6 39
5 3 40
9 4 41
9 7 42
9 6 43
9 3 44
9 10 45
4 7 46
4 6 47
4 3 48
4 10 49
4 1 50
 7 9 2
7 4 1
4 1 2
6 5 3
1 3 4
7 1 5
5 2 6
2 4 7
2 5 8
3 7 9
 6 13 3
3 1 1
6 5 2
4 3 3
1 2 4
2 3 5
2 5 6
5 6 7
3 2 8
5 1 9
2 1 10
5 3 11
3 6 12
4 6 13
 8 24 4
8 2 1
6 7 2
7 3 3
8 1 4
4 7 5
8 7 6
3 6 7
8 4 8
2 1 9
4 8 10
3 4 11
3 5 12
6 4 13
5 4 14
2 6 15
4 2 16
2 8 17
1 5 18
5 7 19
1 8 20
5 6 21
7 5 22
7 6 23
2 7 24
 10 45 7
7 3 1
7 5 2
4 8 3
8 3 4
4 9 5
9 1 6
5 10 7
8 7 8
2 8 9
1 7 10
6 3 11
10 6 12
3 8 13
7 2 14
6 2 15
1 8 16
2 3 17
8 1 18
4 10 19
1 6 20
3 1 21
10 4 22
10 3 23
9 3 24
2 9 25
4 6 26
8 5 27
6 9 28
7 9 29
10 5 30
10 2 31
5 7 32
8 6 33
2 5 34
5 1 35
2 6 36
5 8 37
1 4 38
8 4 39
5 9 40
8 2 41
5 6 42
5 2 43
4 3 44
7 8 45
 6 29 6
6 2 1
5 1 2
2 1 3
5 4 4
6 3 5
3 6 6
1 4 7
5 6 8
5 3 9
2 3 10
3 2 11
6 1 12
6 4 13
3 4 14
2 5 15
6 5 16
3 1 17
4 6 18
1 6 19
1 2 20
4 1 21
1 3 22
5 2 23
2 4 24
4 3 25
4 5 26
4 2 27
3 5 28
1 5 29
 9 63 8
6 9 1
3 6 2
5 9 3
1 9 4
4 9 5
9 6 6
4 3 7
7 1 8
1 7 9
2 1 10
4 8 11
8 5 12
7 6 13
7 4 14
3 9 15
6 8 16
7 2 17
7 5 18
4 6 19
2 4 20
5 4 21
3 4 22
7 3 23
2 9 24
2 6 25
3 5 26
2 8 27
9 1 28
6 5 29
2 3 30
8 4 31
3 2 32
1 6 33
7 9 34
9 8 35
8 2 36
4 1 37
1 3 38
9 3 39
8 7 40
7 8 41
5 7 42
1 2 43
4 5 44
1 4 45
3 1 46
3 7 47
6 3 48
5 6 49
6 4 50
5 2 51
8 9 52
4 7 53
1 5 54
8 1 55
8 3 56
9 2 57
1 8 58
2 5 59
6 7 60
2 7 61
3 8 62
8 6 63
 7 27 6
4 3 1
3 6 2
2 6 3
1 2 4
2 4 5
6 7 6
3 1 7
6 3 8
3 4 9
7 2 10
6 1 11
5 4 12
5 7 13
6 5 14
2 7 15
7 3 16
4 1 17
1 4 18
7 6 19
1 3 20
7 4 21
3 7 22
3 5 23
3 2 24
7 1 25
5 1 26
2 5 27
 8 49 7
5 1 1
4 3 2
2 8 3
3 2 4
6 7 5
7 4 6
8 5 7
5 3 8
4 6 9
2 5 10
1 7 11
3 7 12
1 3 13
8 6 14
6 8 15
4 8 16
3 4 17
8 2 18
6 3 19
8 7 20
2 6 21
3 1 22
5 2 23
8 3 24
6 4 25
7 8 26
3 8 27
5 7 28
5 8 29
3 5 30
1 8 31
7 2 32
1 5 33
2 1 34
5 4 35
2 3 36
4 1 37
8 1 38
5 6 39
6 2 40
6 5 41
3 6 42
1 6 43
1 4 44
6 1 45
2 4 46
4 5 47
2 7 48
8 4 49
 8 52 7
3 1 1
5 1 2
7 2 3
3 8 4
4 1 5
2 5 6
3 6 7
4 3 8
7 4 9
7 8 10
2 1 11
2 4 12
4 7 13
2 7 14
1 4 15
3 7 16
8 1 17
5 4 18
2 8 19
7 3 20
1 3 21
8 2 22
8 3 23
1 5 24
6 3 25
7 6 26
3 2 27
6 2 28
1 2 29
4 8 30
5 8 31
4 5 32
5 3 33
4 6 34
1 8 35
8 6 36
7 5 37
2 6 38
8 7 39
3 4 40
6 1 41
3 5 42
6 4 43
6 5 44
4 2 45
5 7 46
2 3 47
8 4 48
5 6 49
1 7 50
7 1 51
5 2 52
 8 19 5
6 4 1
7 3 2
6 3 3
3 6 4
1 2 5
4 6 6
6 1 7
8 6 8
8 5 9
8 3 10
1 3 11
8 4 12
2 8 13
4 1 14
4 7 15
2 3 16
4 5 17
8 7 18
5 4 19
 7 41 7
7 1 1
7 3 2
3 1 3
6 4 4
2 3 5
2 7 6
3 6 7
7 4 8
1 5 9
7 6 10
5 1 11
6 5 12
2 6 13
5 7 14
4 1 15
4 5 16
4 3 17
1 4 18
1 6 19
6 3 20
4 7 21
1 3 22
7 2 23
2 5 24
1 7 25
5 3 26
3 5 27
6 7 28
3 2 29
3 4 30
3 7 31
2 4 32
6 1 33
5 4 34
6 2 35
7 5 36
5 6 37
2 1 38
5 2 39
4 6 40
1 2 41
 9 36 7
7 4 1
1 6 2
2 3 3
2 8 4
1 3 5
1 9 6
6 2 7
6 3 8
9 7 9
4 3 10
7 6 11
6 5 12
1 4 13
7 9 14
8 2 15
2 5 16
9 6 17
5 2 18
8 5 19
9 8 20
2 6 21
8 7 22
3 5 23
3 6 24
3 4 25
5 9 26
1 8 27
8 3 28
8 6 29
3 1 30
8 4 31
4 8 32
8 1 33
6 1 34
1 7 35
7 2 36
 5 9 2
4 5 1
2 4 2
4 1 3
2 5 4
3 5 5
5 3 6
5 1 7
1 2 8
1 5 9
 10 43 6
4 5 1
8 6 2
1 4 3
1 7 4
3 2 5
3 9 6
6 10 7
2 5 8
7 3 9
8 9 10
10 4 11
9 4 12
7 10 13
2 4 14
6 7 15
2 6 16
4 8 17
9 1 18
10 7 19
7 2 20
9 2 21
10 3 22
8 4 23
9 6 24
10 6 25
5 2 26
8 10 27
8 5 28
9 3 29
5 1 30
5 8 31
6 1 32
3 4 33
9 8 34
4 1 35
4 7 36
5 4 37
4 6 38
1 9 39
7 4 40
2 3 41
8 1 42
4 10 43
 7 14 3
3 2 1
2 5 2
6 7 3
3 7 4
5 4 5
2 7 6
5 7 7
1 3 8
7 6 9
7 2 10
2 6 11
4 1 12
6 4 13
1 5 14
 9 27 4
4 8 1
2 1 2
9 4 3
1 6 4
7 1 5
6 2 6
6 1 7
2 9 8
1 3 9
4 3 10
6 8 11
3 7 12
9 7 13
3 9 14
5 7 15
9 3 16
8 3 17
3 5 18
6 9 19
8 6 20
1 2 21
2 8 22
5 1 23
5 4 24
4 6 25
1 5 26
5 2 27
 10 39 6
10 1 1
2 6 2
4 2 3
8 3 4
3 8 5
2 10 6
1 2 7
6 10 8
7 3 9
7 5 10
10 8 11
6 8 12
5 8 13
8 1 14
1 6 15
4 9 16
9 6 17
9 8 18
10 9 19
5 2 20
7 2 21
3 1 22
5 6 23
1 9 24
6 7 25
8 4 26
1 10 27
6 4 28
6 3 29
2 4 30
3 7 31
2 3 32
8 6 33
3 10 34
5 9 35
4 8 36
6 9 37
1 3 38
4 5 39
 6 24 5
4 6 1
2 4 2
3 4 3
6 2 4
5 3 5
4 3 6
4 2 7
4 5 8
6 4 9
1 3 10
5 6 11
3 2 12
5 2 13
3 1 14
5 1 15
1 5 16
1 4 17
5 4 18
1 6 19
3 5 20
2 6 21
1 2 22
2 1 23
3 3 24
 7 13 2
6 5 1
3 6 2
2 3 3
4 1 4
4 6 5
5 3 6
7 3 7
1 2 2
2 4 9
7 4 10
3 2 11
6 1 12
5 7 13
 10 50 8
7 6 1
7 3 2
7 10 3
7 1 4
7 2 5
6 3 6
6 10 7
6 1 8
6 2 9
6 8 10
3 10 11
3 1 12
3 2 13
3 8 14
3 5 15
10 1 16
10 2 17
10 8 18
10 5 19
10 9 20
2 2 21
1 8 22
1 5 23
1 9 24
1 4 25
2 8 26
2 5 27
2 9 28
2 4 29
2 7 30
8 5 31
8 9 32
8 4 33
8 7 34
8 6 35
5 9 36
5 4 37
5 7 38
5 6 39
5 3 40
9 4 41
9 7 42
9 6 43
9 3 44
9 10 45
4 7 46
4 6 47
4 3 48
4 10 49
4 1 50
 6 29 6
6 2 1
5 1 2
2 2 3
5 4 4
6 3 5
3 6 6
1 4 7
5 6 8
5 3 9
2 3 10
3 2 11
6 1 12
6 4 13
3 4 14
2 5 15
6 5 16
3 1 17
4 6 18
1 6 19
1 2 20
4 1 21
1 3 22
5 2 23
2 4 24
4 3 25
4 5 26
4 2 27
3 5 28
1 5 29
 7 41 7
7 1 1
7 3 2
3 1 3
6 4 4
2 3 5
2 7 6
3 6 7
7 4 8
1 5 9
7 6 10
5 1 11
6 5 12
2 6 13
5 7 14
4 1 15
4 5 16
4 3 17
1 4 18
1 6 19
6 3 20
4 7 21
1 3 22
7 2 23
2 5 24
1 7 25
5 2 26
3 5 27
6 7 28
3 2 29
3 4 30
3 7 31
2 4 32
6 1 33
5 4 34
6 2 35
7 5 36
5 6 37
2 1 38
5 2 39
4 6 40
1 2 41
 9 36 7
7 4 1
1 6 2
2 3 3
2 8 4
1 3 5
1 9 6
6 2 7
6 3 8
9 7 9
4 3 10
7 6 11
6 5 12
1 4 13
7 9 14
8 2 15
2 5 16
9 6 17
5 2 18
8 5 19
9 8 20
2 6 21
8 7 22
3 5 23
3 6 24
3 4 25
5 9 26
1 8 27
8 3 28
8 6 29
3 2 30
8 4 31
4 8 32
8 1 33
6 1 34
1 7 35
7 2 36
 6 13 4
3 5 1
2 5 2
6 3 3
1 4 4
2 6 5
5 3 6
4 1 7
4 3 8
5 2 9
4 4 10
2 1 11
6 1 12
4 6 13
 6 29 6
6 2 1
5 1 2
2 2 3
5 2 4
6 3 5
3 6 6
1 4 7
5 6 8
5 3 9
2 3 10
3 2 11
6 1 12
6 4 13
3 4 14
2 5 15
6 5 16
3 1 17
4 6 18
1 6 19
1 2 20
4 1 21
1 3 22
5 2 23
2 4 24
4 3 25
4 5 26
4 2 27
3 5 28
1 5 29
 6 29 6
6 2 1
5 1 2
2 2 3
5 2 4
6 3 5
3 6 6
1 4 7
1 6 8
5 3 9
2 3 10
3 2 11
6 1 12
6 4 13
3 4 14
2 5 15
6 5 16
3 1 17
4 6 18
1 6 19
1 2 20
4 1 21
1 3 22
5 2 23
2 4 24
4 3 25
4 5 26
4 2 27
3 5 28
1 5 29
 10 50 8
7 6 1
7 3 2
7 10 3
7 1 4
7 2 5
6 3 6
6 10 7
6 1 8
6 2 9
6 8 10
3 10 11
3 1 12
3 2 13
3 8 14
3 5 15
10 1 16
10 2 17
10 8 18
10 5 19
10 9 20
1 2 21
1 8 22
1 5 23
1 9 24
1 4 25
2 8 26
2 5 27
2 9 28
2 4 29
4 7 30
8 5 31
8 9 32
8 4 33
8 7 34
8 6 35
5 9 36
5 4 37
5 7 38
5 6 39
5 3 40
9 4 41
9 7 42
9 6 43
9 3 44
9 10 45
4 7 46
4 6 47
4 3 48
4 10 49
4 1 50
 8 19 5
6 4 1
7 3 2
6 3 3
3 6 4
1 2 5
4 6 6
6 1 7
8 6 8
8 5 9
7 3 10
1 3 11
8 4 12
2 8 13
4 1 14
4 7 15
2 3 16
4 5 17
8 7 18
5 4 19
 7 9 2
7 4 1
4 1 2
6 5 3
1 3 4
7 1 9
5 2 6
2 4 7
2 5 8
3 7 9
 8 24 4
8 2 1
6 7 2
7 3 3
8 1 4
4 7 5
8 7 6
3 6 7
8 4 8
2 1 9
4 8 10
3 4 11
3 5 12
6 4 11
5 4 14
2 6 15
4 2 16
2 8 17
1 5 18
5 7 19
1 8 20
5 6 21
7 5 22
7 6 23
2 7 24
 10 45 7
7 3 1
7 5 2
4 8 3
8 3 4
4 9 5
9 1 7
5 10 7
8 7 8
2 8 9
1 7 10
6 3 11
10 6 12
3 8 13
7 2 14
6 2 15
1 8 16
2 3 17
8 1 18
4 10 19
1 6 20
3 1 21
10 4 22
10 3 23
9 3 24
2 9 25
4 6 26
8 5 27
6 9 28
7 9 29
10 5 30
10 2 31
5 7 32
8 6 33
2 5 34
5 1 35
2 6 36
5 8 37
1 4 38
8 4 39
5 9 40
8 2 41
5 6 42
5 2 43
4 3 44
7 8 45
 5 9 2
4 5 1
2 5 2
4 1 3
2 5 4
3 5 5
5 3 6
5 1 7
1 2 8
1 5 9
 10 43 6
4 5 1
8 6 2
1 4 3
1 7 4
3 2 5
3 9 9
6 10 7
2 5 8
7 3 9
8 9 10
10 4 11
9 4 12
7 10 13
2 4 14
6 7 15
2 6 16
4 8 17
9 1 18
10 7 19
7 2 20
9 2 21
10 3 22
8 4 23
9 6 24
10 6 25
5 2 26
8 10 27
8 5 28
9 3 29
5 1 30
5 8 31
6 1 32
3 4 33
9 8 34
4 1 35
4 7 36
5 4 37
4 6 38
1 9 39
7 4 40
2 3 41
8 1 42
4 10 43
 9 27 4
4 8 2
2 1 2
9 4 3
1 6 4
7 1 5
6 2 6
6 1 7
2 9 8
1 3 9
4 3 10
6 8 11
3 7 12
9 7 13
3 9 14
5 7 15
9 3 16
8 3 17
3 5 18
6 9 19
8 6 20
1 2 21
2 8 22
5 1 23
5 4 24
4 6 25
1 5 26
5 2 27
 10 39 6
10 1 1
2 6 2
4 2 3
8 3 4
3 8 5
2 10 6
1 2 7
6 10 8
7 3 9
7 5 10
10 8 11
6 8 12
5 8 13
8 1 14
1 6 15
4 9 16
9 6 17
9 8 18
10 9 19
5 2 20
7 2 21
3 1 22
5 6 23
1 9 24
6 7 25
8 4 26
1 10 27
6 2 28
6 3 29
2 4 30
3 7 31
2 3 32
8 6 33
3 10 34
5 9 35
4 8 36
6 9 37
1 3 38
4 5 39
 10 43 6
4 5 1
8 6 2
1 4 3
1 7 4
3 2 5
3 9 9
6 10 7
2 5 8
7 3 9
8 9 10
10 4 11
9 4 12
7 10 13
2 4 14
6 7 15
2 6 16
4 8 17
9 1 18
10 7 19
7 2 20
9 2 21
10 3 22
8 4 23
9 6 24
10 6 25
5 2 26
8 10 27
8 5 28
9 3 29
5 1 30
5 8 31
6 1 32
3 4 33
9 8 34
4 1 35
4 7 36
5 4 37
4 6 38
1 9 39
7 4 71
2 3 41
8 1 42
4 10 43
 10 39 6
10 1 1
2 6 2
4 2 3
8 3 4
3 8 5
2 10 6
1 2 7
6 10 8
7 3 9
7 5 10
10 8 11
6 8 12
5 8 13
8 1 14
1 6 15
4 9 16
9 6 17
9 8 18
10 9 19
5 2 20
7 2 21
5 1 22
5 6 23
1 9 24
6 7 25
8 4 26
1 10 27
6 2 28
6 3 29
2 4 30
3 7 31
2 3 32
8 6 33
3 10 34
5 9 35
4 8 36
6 9 37
1 3 38
4 5 39
 10 43 6
4 5 1
8 6 2
1 4 3
1 7 4
3 2 5
3 9 9
6 10 7
2 5 8
7 3 9
8 9 10
10 4 11
9 4 12
7 10 13
2 4 14
6 7 15
2 6 16
4 8 17
9 1 18
10 7 19
7 2 20
9 2 21
10 3 22
8 4 23
9 6 24
10 6 25
5 2 26
8 5 27
8 5 28
9 3 29
5 1 30
5 8 31
6 1 32
3 4 33
9 8 34
4 1 35
4 7 36
5 4 37
4 6 38
1 9 39
7 4 71
2 3 41
8 1 42
4 10 43
 6 12 4
1 4 1
4 5 2
6 1 3
5 1 1
6 4 5
1 3 6
6 5 7
4 2 8
1 5 9
2 1 10
3 6 11
6 2 12
 6 24 5
4 6 1
2 4 2
3 4 3
6 2 4
5 3 5
4 3 6
4 2 7
4 5 8
6 4 9
1 3 10
5 6 11
3 2 12
5 2 13
3 1 14
5 1 15
1 6 16
1 4 17
5 4 18
1 6 19
3 5 20
2 6 21
1 2 22
2 1 23
3 6 24
 7 28 5
2 7 1
4 2 2
7 5 3
3 5 4
6 3 5
5 3 6
7 7 7
1 6 8
3 6 9
2 6 10
4 3 11
1 7 12
1 3 13
5 7 14
2 4 15
7 3 16
5 1 17
3 2 18
5 6 19
4 7 20
6 4 21
1 2 22
2 3 23
1 5 24
4 1 25
7 6 26
7 2 27
6 2 28
 6 13 3
3 1 1
6 5 2
4 3 3
1 2 4
2 1 5
2 5 6
5 6 7
3 2 8
5 1 9
2 1 10
5 3 11
3 6 12
4 6 13
 8 24 4
8 2 1
6 7 2
7 3 3
8 1 4
4 7 5
8 7 6
3 6 7
8 4 8
2 1 9
4 8 10
3 4 11
4 5 12
6 4 13
5 4 14
2 6 15
4 2 16
2 8 17
1 5 18
5 7 19
1 8 20
5 6 21
7 5 22
7 6 23
2 7 24
 10 45 7
7 3 1
7 5 2
4 8 3
8 2 4
4 9 5
9 1 6
5 10 7
8 7 8
2 8 9
1 7 10
6 3 11
10 6 12
3 8 13
7 2 14
6 2 15
1 8 16
2 3 17
8 1 18
4 10 19
1 6 20
3 1 21
10 4 22
10 3 23
9 3 24
2 9 25
4 6 26
8 5 27
6 9 28
7 9 29
10 5 30
10 2 31
5 7 32
8 6 33
2 5 34
5 1 35
2 6 36
5 8 37
1 4 38
8 4 39
5 9 40
8 2 41
5 6 42
5 2 43
4 3 44
7 8 45
 7 14 3
3 2 1
2 5 2
6 7 3
3 7 4
5 4 5
2 7 6
5 7 7
1 3 8
7 6 9
7 2 10
2 6 11
4 1 12
3 4 13
1 5 14
 9 27 4
4 8 1
2 1 2
9 4 3
1 6 4
7 1 5
6 2 6
6 1 7
2 9 8
1 3 9
4 3 10
6 8 11
3 7 12
9 7 13
3 9 14
5 7 15
9 3 16
8 3 17
3 5 18
6 9 19
8 6 3
1 2 21
2 8 22
5 1 23
5 4 24
4 6 25
1 5 26
5 2 27
 10 39 6
10 1 1
2 6 2
4 2 3
8 3 4
3 8 5
2 10 6
1 2 7
6 10 8
7 3 9
7 5 10
10 8 11
6 8 12
5 8 13
8 1 14
1 6 15
4 9 16
9 6 17
9 8 18
10 9 19
5 2 20
7 2 21
3 1 22
5 6 23
1 9 24
6 7 25
8 4 26
1 10 27
6 4 28
6 3 29
2 4 30
3 7 31
2 4 32
8 6 33
3 10 34
5 9 35
4 8 36
6 9 37
1 3 38
4 5 39
 7 13 2
6 5 1
3 6 2
2 3 3
4 1 6
4 6 5
5 3 6
7 3 7
1 2 2
2 4 9
7 4 10
3 2 11
6 1 12
5 7 13
 8 24 4
8 2 1
6 7 2
7 3 3
8 1 4
4 7 5
7 7 6
3 6 7
8 4 8
2 1 9
4 8 10
3 4 11
3 5 12
6 4 11
5 4 14
2 6 15
4 2 16
2 8 17
1 5 18
5 7 19
1 8 20
5 6 21
7 5 22
7 6 23
2 7 24
 10 45 7
7 3 1
7 5 2
4 8 3
8 3 4
4 9 5
9 1 7
5 10 7
8 7 8
2 8 9
1 7 10
6 3 11
10 6 12
3 8 13
7 2 14
6 2 15
1 8 16
2 3 17
8 1 18
4 10 19
1 6 20
3 1 21
10 4 22
10 3 23
9 3 24
2 9 25
4 6 26
8 5 27
6 9 28
7 9 29
2 5 30
10 2 31
5 7 32
8 6 33
2 5 34
5 1 35
2 6 36
5 8 37
1 4 38
8 4 39
5 9 40
8 2 41
5 6 42
5 2 43
4 3 44
7 8 45
 6 29 6
6 2 1
5 1 2
2 2 3
5 4 4
6 3 5
3 6 6
1 4 7
5 6 8
5 3 9
2 3 10
3 2 11
6 1 12
6 4 13
3 4 14
2 6 15
6 5 16
3 1 17
4 6 18
1 6 19
1 2 20
4 1 21
1 3 22
5 2 23
2 4 24
4 3 25
4 5 26
4 2 27
3 5 28
1 5 29
 5 9 2
4 4 1
2 5 2
4 1 3
2 5 4
3 5 5
5 3 6
5 1 7
1 2 8
1 5 9
 10 43 6
4 5 1
8 6 2
1 4 3
1 7 4
3 2 5
3 9 9
6 10 7
2 5 8
7 3 9
8 9 10
10 4 11
9 4 12
7 10 13
2 4 14
6 7 15
2 6 16
4 8 17
9 1 18
10 7 19
7 2 20
9 2 21
10 3 22
8 4 23
9 6 24
10 4 25
5 2 26
8 10 27
8 5 28
9 3 29
5 1 30
5 8 31
6 1 32
3 4 33
9 8 34
4 1 35
4 7 36
5 4 37
4 6 38
1 9 39
7 4 40
2 3 41
8 1 42
4 10 43
 10 39 6
10 1 1
2 6 2
4 2 3
8 3 4
3 8 5
2 10 6
1 2 7
6 10 8
7 3 9
7 5 10
10 8 11
6 8 12
5 8 13
8 1 14
1 6 15
4 9 16
9 6 17
9 8 18
10 9 19
5 2 20
7 2 21
3 1 22
5 6 23
1 9 24
6 7 25
8 7 26
1 10 27
6 2 28
6 3 29
2 4 30
3 7 31
2 3 32
8 6 33
3 10 34
5 9 35
4 8 36
6 9 37
1 3 38
4 5 39
 10 43 6
4 5 1
8 6 2
1 4 3
1 7 4
3 2 5
3 9 9
6 8 7
2 5 8
7 3 9
8 9 10
10 4 11
9 4 12
7 10 13
2 4 14
6 7 15
2 6 16
4 8 17
9 1 18
10 7 19
7 2 20
9 2 21
10 3 22
8 4 23
9 6 24
10 6 25
5 2 26
8 10 27
8 5 28
9 3 29
5 1 30
5 8 31
6 1 32
3 4 33
9 8 34
4 1 35
4 7 36
5 4 37
4 6 38
1 9 39
7 4 71
2 3 41
8 1 42
4 10 43

2
 1
 1
 0
 144
 2
 0
 1
 6
 1
 2
 0
 14
 1
 2
 40320
 0
 0
 0
 0
 72
 48
 3
 24
 24
 2
 168
 10
 0
 0
 1
 0
 0
 2 0 2688 72 168 10 1 36 12 1680 5 0 0 0 0 0 0 0 0 0 0 0 1 2 0 0 0 1 0 1 0 0 0 0 0 0 0 0