#ifndef __GRAPH_H__
#define __GRAPH_H__

#include <cassert>
#include <vector>
#include <algorithm>
#include <limits>
#include <queue>
#include <functional>
#include <utility>
#include <stack>

/* vector<Edge> とその配列で名前変えたほうがいいかも */
/* 辺の重複、自己ループ、辺の削除(負の辺の判定含め) */
/* 辺の探索 */
/* 経路復元 */

using CostType = long long;

struct Edge_ToCost {
	int to;
	CostType cost;
	Edge_ToCost(int to, CostType cost);

	static int Compare_by_cost(const Edge_ToCost& left, const Edge_ToCost& right);

	struct GreaterCost {
		bool operator()(const Edge_ToCost& left, const Edge_ToCost& right);
	};
};

struct Edge_FromToCost {
	int from;
	int to;
	CostType cost;
	Edge_FromToCost(int from, int to, CostType cost);

	static int Compare_by_cost(const Edge_FromToCost& left, const Edge_FromToCost& right);

	struct GreaterCost {
		bool operator()(const Edge_FromToCost& left, const Edge_FromToCost& right);
	};
	struct LessCost {
		bool operator()(const Edge_FromToCost& left, const Edge_FromToCost& right);
	};
};


/* 多重辺、自己ループはない仕様 */
/* 頂点に何かが割り振られているときもあるよね */
class GraphAsListImpl {
public:
	using Edge = Edge_ToCost;
	using List = std::vector<Edge>;
	using Iterator = List::iterator;
	using ConstIterator = List::const_iterator;

protected:
	List* graph_p_m;
	int size_m;

	void Copy(const GraphAsListImpl& other);
	bool Is_valid_vertex(int vertex) const;
public:
	GraphAsListImpl();
	GraphAsListImpl(int size);
	GraphAsListImpl(const GraphAsListImpl& other);
	~GraphAsListImpl();

	GraphAsListImpl& operator=(const GraphAsListImpl& other);
	const List& operator[](int index) const;

	int Size() const;
	void Add(int from, int to, CostType cost, bool bidirected = false);
	Iterator Find(int from, int to);
	ConstIterator Find(int from, int to) const;
	bool Erase(int from, int to);
};

class GraphAsListBidirected;
class GraphAsList {
public:
	using Edge = GraphAsListImpl::Edge;
	using List = GraphAsListImpl::List;
	using Iterator = GraphAsListImpl::Iterator;
	using ConstIterator = GraphAsListImpl::ConstIterator;
private:
	GraphAsListImpl graph_impl_m;
public:
	GraphAsList();
	GraphAsList(int size);
	GraphAsList(const GraphAsList& other);
	GraphAsList(const GraphAsListBidirected& other);
	~GraphAsList();

	GraphAsList& operator=(const GraphAsList& other);
	const List& operator[](int index) const;

	int Size() const;
	void Add(int from, int to, CostType cost = 1, bool bidirected = false);
	Iterator Find(int from, int to);
	ConstIterator Find(int from, int to) const;
	bool Erase(int from, int to, bool bidirected = false);
};


class GraphAsListBidirected {
public:
	/* メンバ関数に対する friend は記述の順番に注意 */
	friend GraphAsList::GraphAsList(const GraphAsListBidirected& other);

	using Edge = GraphAsListImpl::Edge;
	using List = GraphAsListImpl::List;
	using Iterator = GraphAsListImpl::Iterator;
	using ConstIterator = GraphAsListImpl::ConstIterator;
private:
	GraphAsListImpl graph_impl_m;
public:
	GraphAsListBidirected();
	GraphAsListBidirected(int size);
	GraphAsListBidirected(const GraphAsListBidirected& other);
	~GraphAsListBidirected();

	GraphAsListBidirected& operator=(const GraphAsListBidirected& other);
	const List& operator[](int index) const;

	int Size() const;
	void Add(int vertex1, int vertex2, CostType cost = 1);
	std::pair<Iterator, Iterator> Find(int vertex1, int vertex2);
	std::pair<ConstIterator, ConstIterator> Find(int vertex1, int vertex2) const;
	bool Erase(int vertex1, int vertex2);
};

/* 強連結成分分解 */
class SCCsCalculator {
	GraphAsList graph_m;

	int current_m;
	std::vector<int> index_m;
	std::vector<int> lowlink_m;
	std::vector<bool> on_stack_m;
	std::stack<int> stack_m;

	std::vector<std::vector<int>> SCCs_m;

	void Calc_sub_rec(int from);
	void Calc_sub(int start);

	static const int UNVISITED = -1;
public:
	SCCsCalculator(const GraphAsList& graph);
	std::vector<std::vector<int>> Calc();
};

/* 連結性を仮定 */
class LowlinkCalculator {
public:
	using Edge = Edge_FromToCost;
private:
	GraphAsListBidirected graph_m;

	int current_m;
	std::vector<int> index_m;
	std::vector<int> lowlink_m;
	std::vector<int> parent_m;
	//Tree childs;

	void Calc_sub_rec(int from, int parent);
	void Calc_sub(int start);

	static const int UNVISITED = -1;
public:
	LowlinkCalculator(const GraphAsListBidirected& graph);
	void Calc();
	std::vector<Edge> Bridges();
	std::vector<int> Articulations();
};



struct GraphQueueElement {
	CostType distance_m;
	int vertex_m;

	static int Compare(const GraphQueueElement& left, const GraphQueueElement& right);

	GraphQueueElement(CostType distance, int vertex);
	GraphQueueElement(const GraphQueueElement&) = default;
};
bool operator<(const GraphQueueElement& left, const GraphQueueElement& right);
bool operator>(const GraphQueueElement& left, const GraphQueueElement& right);
bool operator<=(const GraphQueueElement& left, const GraphQueueElement& right);
bool operator>=(const GraphQueueElement& left, const GraphQueueElement& right);
bool operator==(const GraphQueueElement& left, const GraphQueueElement& right);
bool operator!=(const GraphQueueElement& left, const GraphQueueElement& right);

std::vector<CostType> Dijkstra(const GraphAsList& graph, int start);
GraphAsListBidirected Prim(const GraphAsListBidirected& graph_arg);
GraphAsListBidirected Kruskal(const GraphAsListBidirected& graph);

#endif
#pragma warning(disable:4996)
#if ONLY_MY_ENVIR
#include "Graph.h"
#include "Union_Find.h"
#endif

#include <queue>

/*-----------------------------------*/
/*---------   Edge_ToCost   ---------*/
/*-----------------------------------*/

Edge_ToCost::Edge_ToCost(int to, CostType cost)
	: to(to), cost(cost) {
}

int Edge_ToCost::Compare_by_cost(const Edge_ToCost& left, const Edge_ToCost& right) {
	if (left.cost > right.cost) return 1;
	if (left.cost < right.cost) return -1;
	if (left.to > right.to) return 1;
	if (left.to < right.to) return -1;
	return 0;
}

bool Edge_ToCost::GreaterCost::operator()(const Edge_ToCost& left, const Edge_ToCost& right) {
	return Compare_by_cost(left, right) > 0;
}

/*---------------------------------------*/
/*---------   Edge_FromToCost   ---------*/
/*---------------------------------------*/

Edge_FromToCost::Edge_FromToCost(int from, int to, CostType cost)
	:from(from), to(to), cost(cost) {
}

int Edge_FromToCost::Compare_by_cost(const Edge_FromToCost & left, const Edge_FromToCost & right) {
	if (left.cost > right.cost) return 1;
	if (left.cost < right.cost) return -1;
	if (left.from > right.from) return 1;
	if (left.from < right.from) return -1;
	if (left.to > right.to) return 1;
	if (left.to < right.to) return -1;
	return 0;
}

bool Edge_FromToCost::GreaterCost::operator()(const Edge_FromToCost & left, const Edge_FromToCost & right) {
	return Compare_by_cost(left, right) > 0;
}

bool Edge_FromToCost::LessCost::operator()(const Edge_FromToCost & left, const Edge_FromToCost & right) {
	return Compare_by_cost(left, right) < 0;
}


/*---------------------------------------*/
/*---------   GraphAsListImpl   ---------*/
/*---------------------------------------*/

void GraphAsListImpl::Copy(const GraphAsListImpl& other) {
	if (graph_p_m == other.graph_p_m) return;
	delete[] graph_p_m;
	size_m = other.size_m;
	graph_p_m = new List[size_m];
	std::copy(other.graph_p_m, other.graph_p_m + size_m, graph_p_m);
}

bool GraphAsListImpl::Is_valid_vertex(int vertex) const {
	return vertex >= 0 && vertex <= size_m;
}

GraphAsListImpl::GraphAsListImpl()
	:size_m(0), graph_p_m(nullptr) {
}

GraphAsListImpl::GraphAsListImpl(int size)
	: size_m(size) {
	graph_p_m = new List[size_m];
}

GraphAsListImpl::GraphAsListImpl(const GraphAsListImpl& other)
	: GraphAsListImpl() {
	Copy(other);
}

GraphAsListImpl::~GraphAsListImpl() {
	delete[] graph_p_m;
}

GraphAsListImpl& GraphAsListImpl::operator=(const GraphAsListImpl& other) {
	Copy(other);
	return *this;
}

const GraphAsListImpl::List& GraphAsListImpl::operator[](int index) const {
	return graph_p_m[index];
}

int GraphAsListImpl::Size() const {
	return size_m;
}

void GraphAsListImpl::Add(int from, int to, CostType cost, bool bidirected) {
	assert(Is_valid_vertex(from) && Is_valid_vertex(to));
	assert(from != to);
	if (bidirected) {
		Add(from, to, cost, false);
		Add(to, from, cost, false);
		return;
	}
	graph_p_m[from].push_back(Edge(to, cost));
}

GraphAsListImpl::Iterator GraphAsListImpl::Find(int from, int to) {
	assert(Is_valid_vertex(from) && Is_valid_vertex(to));
	assert(from != to);
	List& list = graph_p_m[from];
	for (auto it = list.begin(); it != list.end(); ++it) {
		if (it->to == to) return it;
	}
	return list.end();
}

GraphAsListImpl::ConstIterator GraphAsListImpl::Find(int from, int to) const {
	assert(Is_valid_vertex(from) && Is_valid_vertex(to));
	assert(from != to);
	List& list = graph_p_m[from];
	for (auto it = list.begin(); it != list.end(); ++it) {
		if (it->to == to) return it;
	}
	return list.end();
}

bool GraphAsListImpl::Erase(int from, int to) {
	assert(Is_valid_vertex(from) && Is_valid_vertex(to));
	assert(from != to);
	List& list = graph_p_m[from];
	auto it = Find(from, to);
	if (it == graph_p_m[from].end()) return false;
	list.erase(it);
	return true;
}

/*---------------------------*/
/*-----   GraphAsList   -----*/
/*---------------------------*/

GraphAsList::GraphAsList() : graph_impl_m() {}
GraphAsList::GraphAsList(int size) : graph_impl_m(size) {}
GraphAsList::GraphAsList(const GraphAsList& other) : graph_impl_m(other.graph_impl_m) {}
GraphAsList::GraphAsList(const GraphAsListBidirected& other) : graph_impl_m(other.graph_impl_m) {}
GraphAsList::~GraphAsList() {}
GraphAsList& GraphAsList::operator=(const GraphAsList& other) {
	graph_impl_m = other.graph_impl_m;
	return *this;
}

const GraphAsList::List& GraphAsList::operator[](int index) const {
	return graph_impl_m[index];
}

int GraphAsList::Size() const {
	return graph_impl_m.Size();
}

void GraphAsList::Add(int from, int to, CostType cost, bool bidirected) {
	graph_impl_m.Add(from, to, cost, bidirected);
}

GraphAsList::Iterator GraphAsList::Find(int from, int to) {
	return graph_impl_m.Find(from, to);
}

GraphAsList::ConstIterator GraphAsList::Find(int from, int to) const {
	return graph_impl_m.Find(from, to);
}

bool GraphAsList::Erase(int from, int to, bool bidirected) {
	if (bidirected) graph_impl_m.Erase(from, to) && graph_impl_m.Erase(to, from);
	return graph_impl_m.Erase(from, to);
}

/*-------------------------------------*/
/*-----   GraphAsListBidirected   -----*/
/*-------------------------------------*/

GraphAsListBidirected::GraphAsListBidirected() : graph_impl_m() {}
GraphAsListBidirected::GraphAsListBidirected(int size) : graph_impl_m(size) {}
GraphAsListBidirected::GraphAsListBidirected(const GraphAsListBidirected& other) : graph_impl_m(other.graph_impl_m) {}
GraphAsListBidirected::~GraphAsListBidirected() {}

GraphAsListBidirected& GraphAsListBidirected::operator=(const GraphAsListBidirected& other) {
	graph_impl_m = other.graph_impl_m;
	return *this;
}

const GraphAsListBidirected::List& GraphAsListBidirected::operator[](int index) const {
	return graph_impl_m[index];
}

int GraphAsListBidirected::Size() const {
	return graph_impl_m.Size();
}

void GraphAsListBidirected::Add(int vertex1, int vertex2, CostType cost) {
	return graph_impl_m.Add(vertex1, vertex2, cost, true);
}

std::pair<GraphAsListBidirected::Iterator, GraphAsListBidirected::Iterator>
GraphAsListBidirected::Find(int vertex1, int vertex2) {
	return make_pair(graph_impl_m.Find(vertex1, vertex2), graph_impl_m.Find(vertex2, vertex1));
}

std::pair<GraphAsListBidirected::ConstIterator, GraphAsListBidirected::ConstIterator>
GraphAsListBidirected::Find(int vertex1, int vertex2) const {
	return make_pair(graph_impl_m.Find(vertex1, vertex2), graph_impl_m.Find(vertex2, vertex1));
}

bool GraphAsListBidirected::Erase(int vertex1, int vertex2) {
	return graph_impl_m.Erase(vertex1, vertex2) && graph_impl_m.Erase(vertex2, vertex1);
}

/*--------------------------------------*/
/*---------   SCCsCalculator   ---------*/
/*--------------------------------------*/

void SCCsCalculator::Calc_sub_rec(int from) {
	index_m[from] = current_m;
	lowlink_m[from] = current_m;
	++current_m;
	stack_m.push(from);
	on_stack_m[from] = true;

	for (auto&& edge : graph_m[from]) {
		int to = edge.to;
		if (index_m[to] == UNVISITED) {
			Calc_sub_rec(to);
			lowlink_m[from] = std::min(lowlink_m[from], lowlink_m[to]);
		} else if (on_stack_m[to]) {		// この条件何のため？
			lowlink_m[from] = std::min(lowlink_m[from], index_m[to]);
		}
	}

	if (lowlink_m[from] == index_m[from]) {
		SCCs_m.push_back(std::vector<int>());
		int vertex;
		do {
			vertex = stack_m.top();
			stack_m.pop();

			on_stack_m[vertex] = false;
			SCCs_m.back().push_back(vertex);
		} while (vertex != from);
	}
}

void SCCsCalculator::Calc_sub(int start) {
	Calc_sub_rec(start);
}

SCCsCalculator::SCCsCalculator(const GraphAsList& graph)
	: graph_m(graph), current_m(0), index_m(graph.Size(), UNVISITED),
	lowlink_m(graph.Size(), UNVISITED), on_stack_m(graph.Size(), false) {
}

std::vector<std::vector<int>> SCCsCalculator::Calc() {
	const int size = graph_m.Size();
	for (int i = 0; i < size; ++i) {
		if (index_m[i] != UNVISITED) continue;
		Calc_sub(i);
	}
	return SCCs_m;
}

/*-----------------------------------------*/
/*---------   LowlinkCalculator   ---------*/
/*-----------------------------------------*/

void LowlinkCalculator::Calc_sub_rec(int from, int parent) {
	index_m[from] = current_m;
	lowlink_m[from] = current_m;
	++current_m;

	for (auto&& edge : graph_m[from]) {
		int to = edge.to;
		if (to == parent) continue;

		if (index_m[to] == UNVISITED) {
			Calc_sub_rec(to, from);
			lowlink_m[from] = std::min(lowlink_m[from], lowlink_m[to]);
			parent_m[to] = from;
		} else {
			lowlink_m[from] = std::min(lowlink_m[from], index_m[to]);
		}
	}
}

void LowlinkCalculator::Calc_sub(int start) {
	parent_m[start] = start;
	Calc_sub_rec(start, -1);
}

LowlinkCalculator::LowlinkCalculator(const GraphAsListBidirected& graph)
	: graph_m(graph), current_m(0), index_m(graph.Size(), UNVISITED), lowlink_m(graph.Size(), UNVISITED), parent_m(graph.Size()) {
}

void LowlinkCalculator::Calc() {
	const int size = graph_m.Size();
	for (int i = 0; i < size; ++i) {
		if (index_m[i] != UNVISITED) continue;
		Calc_sub(i);
	}
}

std::vector<LowlinkCalculator::Edge> LowlinkCalculator::Bridges() {
	const int size = graph_m.Size();
	std::vector<Edge> ret_vec;
	for (int i = 0; i < size; ++i) {
		int parent = parent_m[i];
		if (parent == i) continue;
		if (lowlink_m[i] > index_m[parent]) {
			int vertex1 = std::min(i, parent);
			int vertex2 = std::max(i, parent);
			ret_vec.push_back(Edge(vertex1, vertex2, 1));
		}
	}
	return ret_vec;
}

std::vector<int> LowlinkCalculator::Articulations() {
	return std::vector<int>();
}



/*----------------------------------*/
/*---------   グローバル   ---------*/
/*----------------------------------*/

int GraphQueueElement::Compare(const GraphQueueElement& left, const GraphQueueElement& right) {
	if (left.distance_m > right.distance_m) return 1;
	if (left.distance_m < right.distance_m) return -1;
	return 0;
}

GraphQueueElement::GraphQueueElement(CostType distance, int vertex)
	: distance_m(distance), vertex_m(vertex) {
}

bool operator<(const GraphQueueElement& left, const GraphQueueElement& right) {
	return GraphQueueElement::Compare(left, right) < 0;
}

bool operator>(const GraphQueueElement& left, const GraphQueueElement& right) {
	return GraphQueueElement::Compare(left, right) > 0;
}

bool operator<=(const GraphQueueElement& left, const GraphQueueElement& right) {
	return GraphQueueElement::Compare(left, right) <= 0;
}

bool operator>=(const GraphQueueElement& left, const GraphQueueElement& right) {
	return GraphQueueElement::Compare(left, right) >= 0;
}

bool operator==(const GraphQueueElement& left, const GraphQueueElement& right) {
	return GraphQueueElement::Compare(left, right) == 0;
}

bool operator!=(const GraphQueueElement& left, const GraphQueueElement& right) {
	return GraphQueueElement::Compare(left, right) != 0;
}

std::vector<CostType> Dijkstra(const GraphAsList& graph, int start) {
	// assert(!Has_negative_edge());

	using Elem = GraphQueueElement;

	const int size = graph.Size();
	const CostType INF_DIST = std::numeric_limits<CostType>::max();
	std::priority_queue<Elem, std::vector<Elem>, std::greater<Elem> > que;

	std::vector<CostType> dist_arr(size, INF_DIST);
	dist_arr[start] = 0;
	que.push(Elem(0, start));

	while (!que.empty()) {
		const Elem curr_pair = que.top();
		que.pop();

		const CostType curr_dist = curr_pair.distance_m;
		const int from = curr_pair.vertex_m;

		if (curr_dist > dist_arr[from]) continue;

		for (auto&& elem : graph[from]) {
			const int to = elem.to;
			const CostType cost = elem.cost;
			const CostType new_dist = curr_dist + cost;

			if (new_dist >= dist_arr[to]) continue;
			dist_arr[to] = new_dist;
			que.push(Elem(new_dist, to));
		}
	}
	return dist_arr;
}


/* 無向グラフとみなしてプリム O(ElogE) */
GraphAsListBidirected Prim(const GraphAsListBidirected& graph_arg) {
	using Edge = Edge_FromToCost;

	const GraphAsList graph(graph_arg);
	const int size = graph.Size();
	bool* used_p = new bool[size];
	std::fill(used_p, used_p + size, false);
	std::priority_queue<Edge, std::vector<Edge>, Edge::GreaterCost> edge_queue;
	
	int start = 0;
	used_p[start] = true;
	for (auto&& edge : graph[start]) {
		edge_queue.push(Edge(start, edge.to, edge.cost));
	}

	int edge_count = 0;
	GraphAsListBidirected ret_graph(size);
	while (edge_count < size - 1) {
		if (edge_queue.empty()) throw std::runtime_error("graph must be connected");
		Edge edge = edge_queue.top(); edge_queue.pop();
		int from = edge.from;
		int to = edge.to;
		CostType cost = edge.cost;
		if (used_p[to]) continue;

		used_p[to] = true;
		ret_graph.Add(from, to, cost);
		for (auto&& new_edge : graph[to]) {
			if (used_p[new_edge.to]) continue;
			edge_queue.push(Edge(to, new_edge.to, new_edge.cost));
		}
		++edge_count;
	}
	delete[] used_p;
	return ret_graph;
}

/* 無向グラフとみなしてクラスカル O(ElogE) */
GraphAsListBidirected Kruskal(const GraphAsListBidirected& graph) {
#ifdef __UNION_FIND_H__
	using Edge = Edge_FromToCost;

	int size = graph.Size();
	UnionFindTree union_find(size);
	std::vector<Edge> edge_arr;

	for (int from = 0; from < size; ++from) {
		for (auto&& edge : graph[from]) {
			if (from > edge.to) continue;
			edge_arr.push_back(Edge(from, edge.to, edge.cost));
		}
	}
	std::sort(edge_arr.begin(), edge_arr.end(), Edge::LessCost());

	GraphAsListBidirected ret_graph(size);
	int edge_count = 0;
	for(auto&& edge : edge_arr) {
		if (edge_count == size - 1) break;
		int from = edge.from;
		int to = edge.to;
		CostType cost = edge.cost;
		if (union_find.Is_same(from, to)) continue;
		ret_graph.Add(from, to, cost);
		union_find.Unite(from, to);
		++edge_count;
	}
	return ret_graph;
#else
#endif
}

#ifndef __INTMOD_H__0001__
#define __INTMOD_H__0001__

#include <vector>
#include <iostream>
#include <cassert>
#include <iostream>

/* Modulus must be less than 0x80000000, and not be 0. */
template <uint32_t Modulus>
class IntMod {
	typedef int32_t Int;
	typedef uint32_t UInt;
	typedef int64_t Long;
	typedef uint64_t ULong;

public:
	template <uint32_t Modulus_>
	friend bool operator==(const IntMod<Modulus_>& left, const IntMod<Modulus_>& right);
	template <uint32_t Modulus_>
	friend bool operator!=(const IntMod<Modulus_>& left, const IntMod<Modulus_>& right);
	template <uint32_t Modulus_>
	friend bool operator<(const IntMod<Modulus_>& left, const IntMod<Modulus_>& right);
	template <uint32_t Modulus_>
	friend bool operator<=(const IntMod<Modulus_>& left, const IntMod<Modulus_>& right);
	template <uint32_t Modulus_>
	friend bool operator>(const IntMod<Modulus_>& left, const IntMod<Modulus_>& right);
	template <uint32_t Modulus_>
	friend bool operator>=(const IntMod<Modulus_>& left, const IntMod<Modulus_>& right);

private:
	UInt value_m;

public:
	IntMod() { value_m = 0; }
	IntMod(UInt value) { value_m = value % Modulus; }
	IntMod(ULong value) { value_m = value % Modulus; }
	IntMod(Int value) {
		Int tmp = value % (Int)Modulus;
		value_m = tmp >= 0 ? tmp : Modulus - (unsigned int)(-tmp);
	}
	IntMod(Long value) {
		Int tmp = value % (Long)Modulus;
		value_m = tmp >= 0 ? tmp : Modulus - (unsigned int)(-tmp);
	}
	IntMod(const IntMod& other) : value_m(other.value_m) {}
	IntMod& operator=(const IntMod& other) { value_m = other.value_m; return *this; }
	
	const IntMod& operator+() const { return *this; }
	IntMod operator-() const { return IntMod(Modulus - value_m); }
	IntMod& operator++() {
		++value_m;
		if (value_m == Modulus) value_m = 0;
		return *this;
	}
	IntMod& operator--() {
		if (value_m == 0) value_m = Modulus;
		--value_m;
		return *this;
	}
	IntMod operator++(int dummy) {
		IntMod tmp(*this);
		++(*this);
		return tmp;
	}
	IntMod operator--(int dummy) {
		IntMod tmp(*this);
		--(*this);
		return tmp;
	}
	IntMod& operator+=(const IntMod& right) {
		value_m += right.value_m;		// value_m < 0x80000000
		if (value_m >= Modulus) value_m -= Modulus;
		return *this;
	}
	IntMod& operator-=(const IntMod& right) {
		if (value_m < right.value_m) value_m += Modulus;
		value_m -= right.value_m;
		return *this;
	}
	IntMod& operator*=(const IntMod& right) {
		value_m = ((ULong)value_m * right.value_m) % Modulus;
		return *this;
	}	
	IntMod& operator/=(const IntMod& right) {
		(*this) *= (right.Inverse());
		return *this;
	}
	// for power
	IntMod operator[](unsigned int exp) const {
		return Pow(exp);
	}

	/* Modulus must be a prime. */
	IntMod Inverse() const { return (*this).Pow(Modulus - 2); }
	IntMod Pow(UInt exp) const {
		IntMod product = 1;
		IntMod factor(*this);
		while (exp > 0) {
			if (exp & 1) product *= factor;
			factor *= factor;
			exp >>= 1;
		}
		return product;
	}
	UInt Get_value() const {
		return value_m;
	}

	static IntMod Fact(UInt num) {
		static std::vector<IntMod> table(1, 1);
		if (table.size() > num) return table[num];

		int old_size = table.size();
		table.resize(num + 1);
		for (int i = old_size; i <= num; i++) {
			table[i] = table[i - 1] * i;
		}
		return table[num];
	}

	static IntMod Combi(UInt n, UInt r) {
		if (n < r) throw "okashii";
		return IntMod::Fact(n) / (IntMod::Fact(n - r) * IntMod::Fact(r));
	}

	static std::vector<IntMod> Inverse_list(int size) {
		assert(size < Modulus);
		std::vector<IntMod> ret_arr(size + 1);
		ret_arr[1] = 1;
		for (int i = 2; i <= size; ++i) {
			ret_arr[i] = ((ULong)(Modulus - Modulus / i) * ret_arr[Modulus % i].Get_value()) % Modulus;
		}
		return ret_arr;
	}
};

template <uint32_t Modulus>
IntMod<Modulus> operator+(const IntMod<Modulus>& left, const IntMod<Modulus>& right) {
	IntMod<Modulus> ret(left);
	ret += right;
	return ret;
}

template <uint32_t Modulus>
IntMod<Modulus> operator-(const IntMod<Modulus>& left, const IntMod<Modulus>& right) {
	IntMod<Modulus> ret(left);
	ret -= right;
	return ret;
}

template <uint32_t Modulus>
IntMod<Modulus> operator*(const IntMod<Modulus>& left, const IntMod<Modulus>& right) {
	IntMod<Modulus> ret(left);
	ret *= right;
	return ret;
}

template <uint32_t Modulus>
IntMod<Modulus> operator/(const IntMod<Modulus>& left, const IntMod<Modulus>& right) {
	IntMod<Modulus> ret(left);
	ret /= right;
	return ret;
}


template <uint32_t Modulus>
bool operator==(const IntMod<Modulus>& left, const IntMod<Modulus>& right) { return left.value_m == right.value_m; }
template <uint32_t Modulus>
bool operator!=(const IntMod<Modulus>& left, const IntMod<Modulus>& right) { return left.value_m != right.value_m; }
/* for set/map */
template <uint32_t Modulus>
bool operator<(const IntMod<Modulus>& left, const IntMod<Modulus>& right) { return left.value_m < right.value_m; }
template <uint32_t Modulus>
bool operator<=(const IntMod<Modulus>& left, const IntMod<Modulus>& right) { return left.value_m <= right.value_m; }
template <uint32_t Modulus>
bool operator>(const IntMod<Modulus>& left, const IntMod<Modulus>& right) { return left.value_m > right.value_m; }
template <uint32_t Modulus>
bool operator>=(const IntMod<Modulus>& left, const IntMod<Modulus>& right) { return left.value_m >= right.value_m; }

template <uint32_t Modulus, class Integer>
IntMod<Modulus> operator+(const IntMod<Modulus>& left, Integer right) { return left + IntMod<Modulus>(right); }
template <uint32_t Modulus, class Integer>
IntMod<Modulus> operator+(Integer left, const IntMod<Modulus>& right) { return IntMod<Modulus>(left) + right; }
template <uint32_t Modulus, class Integer>
IntMod<Modulus> operator-(const IntMod<Modulus>& left, Integer right) { return left - IntMod<Modulus>(right); }
template <uint32_t Modulus, class Integer>
IntMod<Modulus> operator-(Integer left, const IntMod<Modulus>& right) { return IntMod<Modulus>(left) - right; }
template <uint32_t Modulus, class Integer>
IntMod<Modulus> operator*(const IntMod<Modulus>& left, Integer right) { return left * IntMod<Modulus>(right); }
template <uint32_t Modulus, class Integer>
IntMod<Modulus> operator*(Integer left, const IntMod<Modulus>& right) { return IntMod<Modulus>(left) * right; }
template <uint32_t Modulus, class Integer>
IntMod<Modulus> operator/(const IntMod<Modulus>& left, Integer right) { return left / IntMod<Modulus>(right); }
template <uint32_t Modulus, class Integer>
IntMod<Modulus> operator/(Integer left, const IntMod<Modulus>& right) { return IntMod<Modulus>(left) / right; }

template <uint32_t Modulus>
std::istream& operator<<(std::istream& ist, const IntMod<Modulus>& val) {
	uint64_t tmp;
	ist >> tmp;
	val = tmp;
	return ist;
}

template <uint32_t Modulus>
std::ostream& operator<<(std::ostream& ost, const IntMod<Modulus>& val) {
	ost << val.Get_value();
	return ost;
}

typedef IntMod<1000000007> MInt;

#if 1
MInt operator"" _m(unsigned long long num) { return MInt((uint64_t)num); }
#endif

#endif
#define _CRT_SECURE_NO_WARNINGS
#define _SCL_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>
#include <iostream>
#include <string>
#include <vector>
#include <list>
#include <utility>
#include <algorithm>
#include <functional>
#include <cmath>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <iomanip>
#include <sstream>
#include <bitset>
#include <limits>
#include <numeric>
#include <valarray>
#include <fstream>

using namespace std;
typedef unsigned int uint;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<LL, LL> PP;
#define REP(i, a, n) for(LL i = (a), i##_max = (n); i < i##_max; ++i)
#define REM(i, a, n) for(LL i = (LL)(n) - 1, i##min = (a); i >= i##min; --i)
#define ALL(arr) (arr).begin(), (arr).end()
#define FLOAT fixed << setprecision(16)
#define SPEEDUP {cin.tie(NULL); ios::sync_with_stdio(false);}
const int INF = 0x3FFFFFFF;
const LL INFLL = 0x3FFFFFFF3FFFFFFF;
const double INFD = 1.0e+308;
const string INFSTR = "\x7f";
const double EPS = 1.0e-9;

void YesNo(bool b) { cout << (b ? "Yes" : "No") << endl; }
void YESNO(bool b) { cout << (b ? "YES" : "NO") << endl; }
template <class T, class U>
istream& operator>>(istream& ist, pair<T, U>& right) { return ist >> right.first >> right.second; }
template <class T, class U>
ostream& operator<<(ostream& ost, const pair<T, U>& right) { return ost << right.first << ' ' << right.second; }
template <class T, class TCompatible, size_t N>
void Fill(T(&dest)[N], const TCompatible& val) { fill(dest, dest + N, val); }
template <class T, class TCompatible, size_t M, size_t N>
void Fill(T(&dest)[M][N], const TCompatible& val) { for (int i = 0; i < M; ++i) Fill(dest[i], val); }
template<class T>
T Compare(T left, T right) { return left > right ? 1 : (left < right ? -1 : 0); }
istream& Ignore(istream& ist) { string s; ist >> s; return ist; }
bool Inside(int i, int j, int h, int w) { return i >= 0 && i < h && j >= 0 && j < w; }
template <class T>
T Next() { T buf; cin >> buf; return buf; }

#ifdef ONLY_MY_ENVIR
#include "IntMod.h"
#include "Union_Find.h"
#include "Graph.h"
#include "Range.h"
#include "Global.h"
#include "Flow_Solver.h"
#include "Tree.h"
#include "Suffix_Array.h"
#include "Geometry.h"
#include "Matrix.h"
#include "Segment_Tree.h"
#include "Rational.h"
#endif

#ifdef __GNUC__
typedef __int128 LLL;
istream& operator>> (istream& ist, __int128& val) { LL tmp;  ist >> tmp; val = tmp; return ist; }
ostream& operator<< (ostream& ost, __int128 val) { LL tmp = val; ost << tmp; return ost; }
#endif

#if 1234567891
#include <array>
#include <random>
#include <unordered_set>
#include <unordered_map>
template<typename T>
using PriorityQ = priority_queue<T, vector<T>, greater<T> >;	// コスト小を優先
template <class T>
auto Is(const T& value) { return [value](const auto& comparand) -> bool { return comparand == value; }; }
#endif

int N, M;
LL X;
int parent[1000];
LL costp[1000];
int depth[1000];
GraphAsListBidirected H;

int A[2000];
int B[2000];
LL C[2000];

void DFS(int from, int prev) {
	for (auto e : H[from]) {
		if (e.to == prev) continue;
		parent[e.to] = from;
		depth[e.to] = depth[from] + 1;
		costp[e.to] = e.cost;
		DFS(e.to, from);
	}
}

int LCA(int i, int j) {
	int di = depth[i];
	int dj = depth[j];
	if (depth[i] > depth[j]) return LCA(j, i);

	int p = i;
	int q = j;
	REP(k, 0, dj - di) {
		q = parent[q];
	}

	while (p != q) {
		p = parent[p];
		q = parent[q];
	}
	return p;
}

LL Max_edge(int i, int j) {
	int r = LCA(i, j);
	LL mx = 0;
	int p = i;
	int q = j;
	while (p != r) {
		mx = max(mx, costp[p]);
		p = parent[p];
	}
	while (q != r) {
		mx = max(mx, costp[q]);
		q = parent[q];
	}
	return mx;
}

int main() {
	cin >> N >> M >> X;
	GraphAsListBidirected G(N);
	
	REP(i, 0, M) {
		cin >> A[i] >> B[i] >> C[i];
		--A[i]; --B[i];
		G.Add(A[i], B[i], C[i]);
	}

	H = Prim(G);
	DFS(0, -1);
	parent[0] = -1;
	costp[0] = 0;

	LL diff[2000];
	PP sub[2000];
	REP(i, 0, M) {
		diff[i] = C[i] - Max_edge(A[i], B[i]);
		sub[i] = PP(diff[i], i);
	}
	
	sort(sub, sub + M);

	LL sum = 0;
	REP(i, 0, N) {
		sum += costp[i];
	}
	LL remain = X - sum;

	int less = 0, eq = 0, greater = 0;
	REP(i, 0, M) {
		int contains = false;
		int k = sub[i].second;
		
		for (auto e : H[A[k]]) {
			if (e.to == B[k]) {
				contains = true;
			}
		}
		for (auto e : H[B[k]]) {
			if (e.to == A[k]) {
				contains = true;
			}
		}

		int diffc = sub[i].first;
		if (diffc < remain || contains) {
			++less;
		} else if (diffc <= remain) {
			++eq;
		} else {
			++greater;
		}
	}

	if (remain == 0) {
		cout << (2_m[less + eq] - 2) * 2_m[M - (less + eq)] << endl;
	} else {
		cout << (2_m[eq] - 1) * 2_m[greater + 1] << endl;
	}
	return 0;
}



Measured memory_bytes: 640