#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
const double pi = acos(-1.0);
template <class T>
long long chkmin(T &a, T b) {
  return a > b ? a = b, 1 : 0;
}
template <class T>
long long chkmax(T &a, T b) {
  return a < b ? a = b, 1 : 0;
}
template <class T>
T sqr(T a) {
  return a * a;
}
template <class T>
T mmin(T a, T b) {
  return a < b ? a : b;
}
template <class T>
T mmax(T a, T b) {
  return a > b ? a : b;
}
template <class T>
T aabs(T a) {
  return a < 0 ? -a : a;
}
template <class T>
long long dcmp(T a, T b) {
  return a > b;
}
template <long long *a>
long long cmp_a(long long first, long long second) {
  return a[first] < a[second];
}
namespace io {
const long long SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c,
                                       qu[55];
long long f, qr;
inline void flush() {
  fwrite(obuf, 1, oS - obuf, stdout);
  oS = obuf;
}
inline void putc(char first) {
  *oS++ = first;
  if (oS == oT) flush();
}
inline bool read(signed &first) {
  for (f = 1, c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                              (iS == iT ? EOF : *iS++))
                            : *iS++);
       c < '0' || c > '9';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    if (c == '-')
      f = -1;
    else if (c == EOF)
      return 0;
  for (first = 0; c <= '9' && c >= '0';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    first = first * 10 + (c & 15);
  first *= f;
  return 1;
}
inline bool read(long long &first) {
  for (f = 1, c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                              (iS == iT ? EOF : *iS++))
                            : *iS++);
       c < '0' || c > '9';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    if (c == '-')
      f = -1;
    else if (c == EOF)
      return 0;
  for (first = 0; c <= '9' && c >= '0';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    first = first * 10 + (c & 15);
  first *= f;
  return 1;
}
inline bool read(char &first) {
  first = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                       (iS == iT ? EOF : *iS++))
                    : *iS++);
  return first != EOF;
}
inline bool read(char *first) {
  while ((*first = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                                (iS == iT ? EOF : *iS++))
                             : *iS++)) == '\n' ||
         *first == ' ' || *first == '\r')
    if (*first == EOF) return 0;
  while (!(*first == '\n' || *first == ' ' || *first == '\r' || *first == EOF))
    *(++first) = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                              (iS == iT ? EOF : *iS++))
                           : *iS++);
  *first = 0;
  return 1;
}
template <typename A, typename... B>
inline bool read(A &first, B &...second) {
  return read(first) && read(second...);
}
inline bool write(signed first) {
  if (!first) putc('0');
  if (first < 0) putc('-'), first = -first;
  while (first) qu[++qr] = first % 10 + '0', first /= 10;
  while (qr) putc(qu[qr--]);
  return 0;
}
inline bool write(long long first) {
  if (!first) putc('0');
  if (first < 0) putc('-'), first = -first;
  while (first) qu[++qr] = first % 10 + '0', first /= 10;
  while (qr) putc(qu[qr--]);
  return 0;
}
inline bool write(char first) {
  putc(first);
  return 0;
}
inline bool write(const char *first) {
  while (*first) {
    putc(*first);
    ++first;
  }
  return 0;
}
inline bool write(char *first) {
  while (*first) {
    putc(*first);
    ++first;
  }
  return 0;
}
template <typename A, typename... B>
inline bool write(A first, B... second) {
  return write(first) || write(second...);
}
struct Flusher_ {
  ~Flusher_() { flush(); }
} io_flusher_;
}  // namespace io
using io ::putc;
using io ::read;
using io ::write;
long long inf;
struct _init_ {
  _init_() { memset(&inf, 0x3f, sizeof(inf)); }
};
_init_ ___INIT__;
long long f[131072], g[131072], s;
long long f2[131072], g2[131072];
vector<pair<long long, long long> > to[100005];
const long long p = 1000000007;
const long long p2 = 19260817;
long long fa[100005], fw[100005];
long long dfn[100005], t;
const long long i2 = 500000004;
const long long i22 = 9630409;
void FWT(long long *a, long long n) {
  for (long long i = 1; i < n; i <<= 1) {
    for (long long j = 0; j < n; j += i + i) {
      for (long long k = 0; k < i; ++k) {
        long long u = a[j + k], v = a[j + k + i];
        a[j + k] = (u + v) % p;
        a[j + k + i] = (u - v + p) % p;
      }
    }
  }
}
void iFWT(long long *a, long long n) {
  for (long long i = 1; i < n; i <<= 1) {
    for (long long j = 0; j < n; j += i + i) {
      for (long long k = 0; k < i; ++k) {
        long long u = a[j + k], v = a[j + k + i];
        a[j + k] = (u + v) * i2 % p;
        a[j + k + i] = (u - v + p) * i2 % p;
      }
    }
  }
}
void FWT2(long long *a, long long n) {
  for (long long i = 1; i < n; i <<= 1) {
    for (long long j = 0; j < n; j += i + i) {
      for (long long k = 0; k < i; ++k) {
        long long u = a[j + k], v = a[j + k + i];
        a[j + k] = (u + v) % p2;
        a[j + k + i] = (u - v + p2) % p2;
      }
    }
  }
}
void iFWT2(long long *a, long long n) {
  for (long long i = 1; i < n; i <<= 1) {
    for (long long j = 0; j < n; j += i + i) {
      for (long long k = 0; k < i; ++k) {
        long long u = a[j + k], v = a[j + k + i];
        a[j + k] = (u + v) * i22 % p2;
        a[j + k + i] = (u - v + p2) * p2 % p2;
      }
    }
  }
}
void dfs(long long first, long long ff) {
  fa[first] = ff;
  dfn[first] = ++t;
  for (auto i : to[first])
    if (i.first != ff) {
      if (!dfn[i.first]) {
        fw[i.first] = i.second;
        s ^= i.second;
        dfs(i.first, first);
      } else if (dfn[i.first] < dfn[first]) {
        g[0] = 1;
        g2[0] = 1;
        long long xo = i.second;
        for (long long j = first; j != i.first; j = fa[j]) {
          ++g[fw[j] ^ xo];
          ++g2[fw[j] ^ xo];
        }
        FWT(g, 1 << 17);
        FWT2(g2, 1 << 17);
        for (long long i = 0; i < 1 << 17; ++i) {
          f[i] = f[i] * g[i] % p;
          g[i] = 0;
          f2[i] = f2[i] * g2[i] % p2;
          g2[i] = 0;
        }
      }
    }
}
signed main() {
  long long n, m, u, v, w;
  read(n, m);
  for (; m; --m) {
    read(u, v, w);
    to[u].push_back(make_pair(v, w));
    to[v].push_back(make_pair(u, w));
  }
  s = 0;
  for (long long i = 0; i < 1 << 17; ++i) {
    f[i] = 1;
    f2[i] = 1;
  }
  dfs(1, 0);
  g[s] = 1;
  FWT(g, 1 << 17);
  for (long long i = 0; i < 1 << 17; ++i) f[i] = f[i] * g[i] % p;
  iFWT(f, 1 << 17);
  g2[s] = 1;
  FWT2(g2, 1 << 17);
  for (long long i = 0; i < 1 << 17; ++i) f2[i] = f2[i] * g2[i] % p2;
  iFWT2(f2, 1 << 17);
  for (long long i = 0; i < 1 << 17; ++i)
    if (f2[i] || f[i]) {
      write(i, ' ', f[i], '\n');
      return 0;
    }
  return 0;
}

### Prompt

Please provide a cpp coded solution to the problem described below:

In the galaxy far far away is the ancient interplanetary republic of Bubbleland, consisting of N planets. Between them, there are M bidirectional wormholes, each connecting a pair of planets. Bubbleland is a very centralized republic, having a capital planet Whiteplanet, from which any another planet can be reached using these wormholes. It is also guaranteed that no wormhole connects planet to itself and that no two different wormholes connect same pair of planets. 

We call a path that begins at one planet, visits other planets and each of them at most once and returns to starting point a tour. Interplanetary Safety Regulations guarantee that each planet belongs to at most one tour and that there are at most 42 tours.

After many eons of usage, wormholes need to be repaired and each wormhole has the cost W_{i} which needs to be payed for reparation. Unfortunately, the Senate of Bubbleland is short on budget. Therefore, they have decided only to fix as many wormholes as they need in order to have all planets reachable from capital and to pay as little money as they have to for this repair. However the way in which the Senate calculates the cost is different. Cost of the set of reparations is binary xor of costs of each individual reparation, that is if reparations to be made have costs A_{1},A_{2},...,A_{k}, the cost of entire set is A_{1} ⊕ A_{2} ⊕ ... ⊕ A_{k}.

Now the Senate would like to know how much money do they have to pay and also the number of different ways to achieve that cost modulo 1000000007.

Input

First line of input contains two numbers N (1 ≤ N ≤ 100.000), the number of planets and M (1 ≤ M ≤ 100.041), the number of wormholes. Following M lines contain three numbers U, V (1 ≤ U ≠ V ≤ N) and W (1 ≤ W ≤ 100.000), meaning that there exists a wormhole connecting planets U and V, with repair cost of W.

Output

Output two numbers, the smallest possible cost of entire reparation and the number of different valid reparations with that cost modulo 1000000007.

Example

Input


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


Output


1 1

Note

We can repair wormholes 1,2,3,5 and 6, paying 5 ⊕ 1⊕ 2 ⊕ 3 ⊕ 4=1, one can check that this is the cheapest repair in which all of the planets are connected and the only valid repair with that cost.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-8;
const double pi = acos(-1.0);
template <class T>
long long chkmin(T &a, T b) {
  return a > b ? a = b, 1 : 0;
}
template <class T>
long long chkmax(T &a, T b) {
  return a < b ? a = b, 1 : 0;
}
template <class T>
T sqr(T a) {
  return a * a;
}
template <class T>
T mmin(T a, T b) {
  return a < b ? a : b;
}
template <class T>
T mmax(T a, T b) {
  return a > b ? a : b;
}
template <class T>
T aabs(T a) {
  return a < 0 ? -a : a;
}
template <class T>
long long dcmp(T a, T b) {
  return a > b;
}
template <long long *a>
long long cmp_a(long long first, long long second) {
  return a[first] < a[second];
}
namespace io {
const long long SIZE = (1 << 21) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = oS + SIZE - 1, c,
                                       qu[55];
long long f, qr;
inline void flush() {
  fwrite(obuf, 1, oS - obuf, stdout);
  oS = obuf;
}
inline void putc(char first) {
  *oS++ = first;
  if (oS == oT) flush();
}
inline bool read(signed &first) {
  for (f = 1, c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                              (iS == iT ? EOF : *iS++))
                            : *iS++);
       c < '0' || c > '9';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    if (c == '-')
      f = -1;
    else if (c == EOF)
      return 0;
  for (first = 0; c <= '9' && c >= '0';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    first = first * 10 + (c & 15);
  first *= f;
  return 1;
}
inline bool read(long long &first) {
  for (f = 1, c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                              (iS == iT ? EOF : *iS++))
                            : *iS++);
       c < '0' || c > '9';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    if (c == '-')
      f = -1;
    else if (c == EOF)
      return 0;
  for (first = 0; c <= '9' && c >= '0';
       c = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                       (iS == iT ? EOF : *iS++))
                     : *iS++))
    first = first * 10 + (c & 15);
  first *= f;
  return 1;
}
inline bool read(char &first) {
  first = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                       (iS == iT ? EOF : *iS++))
                    : *iS++);
  return first != EOF;
}
inline bool read(char *first) {
  while ((*first = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                                (iS == iT ? EOF : *iS++))
                             : *iS++)) == '\n' ||
         *first == ' ' || *first == '\r')
    if (*first == EOF) return 0;
  while (!(*first == '\n' || *first == ' ' || *first == '\r' || *first == EOF))
    *(++first) = (iS == iT ? (iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
                              (iS == iT ? EOF : *iS++))
                           : *iS++);
  *first = 0;
  return 1;
}
template <typename A, typename... B>
inline bool read(A &first, B &...second) {
  return read(first) && read(second...);
}
inline bool write(signed first) {
  if (!first) putc('0');
  if (first < 0) putc('-'), first = -first;
  while (first) qu[++qr] = first % 10 + '0', first /= 10;
  while (qr) putc(qu[qr--]);
  return 0;
}
inline bool write(long long first) {
  if (!first) putc('0');
  if (first < 0) putc('-'), first = -first;
  while (first) qu[++qr] = first % 10 + '0', first /= 10;
  while (qr) putc(qu[qr--]);
  return 0;
}
inline bool write(char first) {
  putc(first);
  return 0;
}
inline bool write(const char *first) {
  while (*first) {
    putc(*first);
    ++first;
  }
  return 0;
}
inline bool write(char *first) {
  while (*first) {
    putc(*first);
    ++first;
  }
  return 0;
}
template <typename A, typename... B>
inline bool write(A first, B... second) {
  return write(first) || write(second...);
}
struct Flusher_ {
  ~Flusher_() { flush(); }
} io_flusher_;
}  // namespace io
using io ::putc;
using io ::read;
using io ::write;
long long inf;
struct _init_ {
  _init_() { memset(&inf, 0x3f, sizeof(inf)); }
};
_init_ ___INIT__;
long long f[131072], g[131072], s;
long long f2[131072], g2[131072];
vector<pair<long long, long long> > to[100005];
const long long p = 1000000007;
const long long p2 = 19260817;
long long fa[100005], fw[100005];
long long dfn[100005], t;
const long long i2 = 500000004;
const long long i22 = 9630409;
void FWT(long long *a, long long n) {
  for (long long i = 1; i < n; i <<= 1) {
    for (long long j = 0; j < n; j += i + i) {
      for (long long k = 0; k < i; ++k) {
        long long u = a[j + k], v = a[j + k + i];
        a[j + k] = (u + v) % p;
        a[j + k + i] = (u - v + p) % p;
      }
    }
  }
}
void iFWT(long long *a, long long n) {
  for (long long i = 1; i < n; i <<= 1) {
    for (long long j = 0; j < n; j += i + i) {
      for (long long k = 0; k < i; ++k) {
        long long u = a[j + k], v = a[j + k + i];
        a[j + k] = (u + v) * i2 % p;
        a[j + k + i] = (u - v + p) * i2 % p;
      }
    }
  }
}
void FWT2(long long *a, long long n) {
  for (long long i = 1; i < n; i <<= 1) {
    for (long long j = 0; j < n; j += i + i) {
      for (long long k = 0; k < i; ++k) {
        long long u = a[j + k], v = a[j + k + i];
        a[j + k] = (u + v) % p2;
        a[j + k + i] = (u - v + p2) % p2;
      }
    }
  }
}
void iFWT2(long long *a, long long n) {
  for (long long i = 1; i < n; i <<= 1) {
    for (long long j = 0; j < n; j += i + i) {
      for (long long k = 0; k < i; ++k) {
        long long u = a[j + k], v = a[j + k + i];
        a[j + k] = (u + v) * i22 % p2;
        a[j + k + i] = (u - v + p2) * p2 % p2;
      }
    }
  }
}
void dfs(long long first, long long ff) {
  fa[first] = ff;
  dfn[first] = ++t;
  for (auto i : to[first])
    if (i.first != ff) {
      if (!dfn[i.first]) {
        fw[i.first] = i.second;
        s ^= i.second;
        dfs(i.first, first);
      } else if (dfn[i.first] < dfn[first]) {
        g[0] = 1;
        g2[0] = 1;
        long long xo = i.second;
        for (long long j = first; j != i.first; j = fa[j]) {
          ++g[fw[j] ^ xo];
          ++g2[fw[j] ^ xo];
        }
        FWT(g, 1 << 17);
        FWT2(g2, 1 << 17);
        for (long long i = 0; i < 1 << 17; ++i) {
          f[i] = f[i] * g[i] % p;
          g[i] = 0;
          f2[i] = f2[i] * g2[i] % p2;
          g2[i] = 0;
        }
      }
    }
}
signed main() {
  long long n, m, u, v, w;
  read(n, m);
  for (; m; --m) {
    read(u, v, w);
    to[u].push_back(make_pair(v, w));
    to[v].push_back(make_pair(u, w));
  }
  s = 0;
  for (long long i = 0; i < 1 << 17; ++i) {
    f[i] = 1;
    f2[i] = 1;
  }
  dfs(1, 0);
  g[s] = 1;
  FWT(g, 1 << 17);
  for (long long i = 0; i < 1 << 17; ++i) f[i] = f[i] * g[i] % p;
  iFWT(f, 1 << 17);
  g2[s] = 1;
  FWT2(g2, 1 << 17);
  for (long long i = 0; i < 1 << 17; ++i) f2[i] = f2[i] * g2[i] % p2;
  iFWT2(f2, 1 << 17);
  for (long long i = 0; i < 1 << 17; ++i)
    if (f2[i] || f[i]) {
      write(i, ' ', f[i], '\n');
      return 0;
    }
  return 0;
}

```