Guy-Manuel and Thomas are planning 144 trips around the world.

You are given a simple weighted undirected connected graph with n vertexes and m edges with the following restriction: there isn't any simple cycle (i. e. a cycle which doesn't pass through any vertex more than once) of length greater than 3 which passes through the vertex 1. The cost of a path (not necessarily simple) in this graph is defined as the [XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) of weights of all edges in that path with each edge being counted as many times as the path passes through it.

But the trips with cost 0 aren't exciting.

You may choose any subset of edges incident to the vertex 1 and remove them. How many are there such subsets, that, when removed, there is not any nontrivial cycle with the cost equal to 0 which passes through the vertex 1 in the resulting graph? A cycle is called nontrivial if it passes through some edge odd number of times. As the answer can be very big, output it modulo 10^9+7.

Input

The first line contains two integers n and m (1 ≤ n,m ≤ 10^5) — the number of vertexes and edges in the graph. The i-th of the next m lines contains three integers a_i, b_i and w_i (1 ≤ a_i, b_i ≤ n, a_i ≠ b_i, 0 ≤ w_i < 32) — the endpoints of the i-th edge and its weight. It's guaranteed there aren't any multiple edges, the graph is connected and there isn't any simple cycle of length greater than 3 which passes through the vertex 1.

Output

Output the answer modulo 10^9+7.

Examples

Input


6 8
1 2 0
2 3 1
2 4 3
2 6 2
3 4 8
3 5 4
5 4 5
5 6 6


Output


2


Input


7 9
1 2 0
1 3 1
2 3 9
2 4 3
2 5 4
4 5 7
3 6 6
3 7 7
6 7 8


Output


1


Input


4 4
1 2 27
1 3 1
1 4 1
3 4 0


Output


6

Note

The pictures below represent the graphs from examples. <image> In the first example, there aren't any nontrivial cycles with cost 0, so we can either remove or keep the only edge incident to the vertex 1. <image> In the second example, if we don't remove the edge 1-2, then there is a cycle 1-2-4-5-2-1 with cost 0; also if we don't remove the edge 1-3, then there is a cycle 1-3-2-4-5-2-3-1 of cost 0. The only valid subset consists of both edges. <image> In the third example, all subsets are valid except for those two in which both edges 1-3 and 1-4 are kept.
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
namespace _buff {
const size_t BUFF = 1 << 19;
char ibuf[BUFF], *ib = ibuf, *ie = ibuf;
char getc() {
  if (ib == ie) {
    ib = ibuf;
    ie = ibuf + fread(ibuf, 1, BUFF, stdin);
  }
  return ib == ie ? -1 : *ib++;
}
}  // namespace _buff
LL read() {
  using namespace _buff;
  LL ret = 0;
  bool pos = true;
  char c = getc();
  for (; (c < '0' || c > '9') && c != '-'; c = getc()) {
    assert(~c);
  }
  if (c == '-') {
    pos = false;
    c = getc();
  }
  for (; c >= '0' && c <= '9'; c = getc()) {
    ret = (ret << 3) + (ret << 1) + (c ^ 48);
  }
  return pos ? ret : -ret;
}
using uint = unsigned;
const size_t N = 1e5 + 5;
const size_t M = N << 1;
const size_t B = 375;
const uint L = 5;
const uint W = 32;
const uint MOD = 1e9 + 7;
using uchar = unsigned char;
void iadd(uint &dp, const uint &val) {
  dp += val;
  if (dp >= MOD) {
    dp -= MOD;
  }
}
uint id[1 << 15], tot;
bool add(uchar b[L], uchar x) {
  for (uint i = L; i--;) {
    if (x >> i & 1u) {
      if (!b[i]) {
        b[i] = x;
        for (uint j = 0; j < i; ++j) {
          if (b[i] >> j & 1u) {
            b[i] ^= b[j];
          }
        }
        for (uint j = i + 1; j < L; ++j) {
          if (b[j] >> i & 1u) {
            b[j] ^= b[i];
          }
        }
        return true;
      } else {
        x ^= b[i];
      }
    }
  }
  return false;
}
uint get_id(uchar b[L]) {
  return b[0] | (b[1] << 1) | (b[2] << 3) | (b[3] << 6) | (b[4] << 10);
}
uchar b[B][L];
uint trans[B][B];
void prep() {
  queue<uint> que;
  que.emplace(id[0] = ++tot);
  while (!que.empty()) {
    uint u = que.front();
    que.pop();
    for (uint i = 1; i < W; ++i) {
      static uchar bb[L];
      memcpy(bb, b[u], sizeof bb);
      if (!add(bb, i)) continue;
      uint v = get_id(bb);
      if (!id[v]) {
        que.emplace(id[v] = ++tot);
        memcpy(b[tot], bb, sizeof bb);
      }
    }
  }
  for (uint i = 1; i <= tot; ++i) {
    for (uint j = 1; j <= i; ++j) {
      static uchar bb[L];
      memcpy(bb, b[i], sizeof bb);
      bool flag = true;
      for (uint k = 0; k < L && flag; ++k) {
        if (b[j][k]) {
          flag = add(bb, b[j][k]);
        }
      }
      if (flag) {
        trans[i][j] = trans[j][i] = id[get_id(bb)];
      }
    }
  }
}
uint head[N], to[M], wei[M], nxt[M], tot_e;
void add_edge(uint u, uint v, uint w) {
  ++tot_e;
  to[tot_e] = v;
  wei[tot_e] = w;
  nxt[tot_e] = head[u];
  head[u] = tot_e;
}
bool block[N], oncyc[N];
uint sum[N], cyc_u[N], cyc_v[N], cyc_w[N], tot_cyc;
void dfs(uint &id, uint u, uint p = 1) {
  static uint dep[N];
  dep[u] = dep[p] + 1;
  for (uint i = head[u]; i; i = nxt[i]) {
    if (to[i] == p) continue;
    uint v = to[i], w = wei[i];
    if (block[v] && block[u]) {
      oncyc[u] = oncyc[v] = true;
      if (u < v) {
        cyc_u[tot_cyc] = u;
        cyc_v[tot_cyc] = v;
        cyc_w[tot_cyc] = sum[u] ^ sum[v] ^ w;
        ++tot_cyc;
      }
      continue;
    }
    if (dep[v] > dep[u]) {
      uint val = sum[u] ^ sum[v] ^ w;
      id = val ? trans[id][val + 1] : 0;
    } else if (!dep[v]) {
      sum[v] = sum[u] ^ w;
      dfs(id, v, u);
    }
  }
}
int main() {
  prep();
  read();
  uint m = read();
  while (m--) {
    uint u = read(), v = read(), w = read();
    add_edge(u, v, w);
    add_edge(v, u, w);
  }
  for (uint i = head[1]; i; i = nxt[i]) {
    block[to[i]] = true;
    sum[to[i]] = wei[i];
  }
  static uint dp[512], idx[N];
  dp[1] = 1;
  for (uint i = head[1]; i; i = nxt[i]) {
    uint v = to[i];
    dfs(idx[v] = 1, v);
    if (!oncyc[v] && idx[v]) {
      for (uint i = B; --i;) {
        iadd(dp[trans[idx[v]][i]], dp[i]);
      }
    }
  }
  for (uint i = 0; i < tot_cyc; ++i) {
    uint u = cyc_u[i], v = cyc_v[i], cyc = cyc_w[i];
    uint id1 = trans[idx[u]][idx[v]];
    uint id2 = cyc ? trans[id1][cyc + 1] : 0;
    if (id1) {
      for (uint i = B, cur; --i;) {
        if ((cur = dp[i])) {
          iadd(dp[trans[id1][i]], cur);
          iadd(dp[trans[id1][i]], cur);
          if (id2) {
            iadd(dp[trans[id2][i]], cur);
          }
        }
      }
    }
  }
  uint ans = 0;
  for (uint i = 1; i < B; ++i) {
    iadd(ans, dp[i]);
  }
  cout << ans;
  return 0;
}
