Problem: Problem

You were asked by your friend Tousa the day before yesterday. He wants to decorate a tree with an arithmetic progression and use it for a birthday party, but the tree is too big to be used alone. Therefore, he wants you, an excellent programmer, to write a program that efficiently decorates a tree with arithmetic progressions. You and Tousa are old friends. You decide to accept Tousa's request.

You will be given a tree of $ N $ nodes to decorate. The nodes of the tree are numbered from $ 0 $ to $ N-1 $. Initially, all tree nodes score $ 0 $. The program must respond to the following two queries:

* $ 0 $. Finds the sum of the points written on the nodes of the specified section of the tree.
* $ 1 $. Adds an arithmetic progression to the nodes in the specified section of the tree.



Beautifully decorate the trees to celebrate Tousa's birthday.

Constraints

The input satisfies the following conditions.

* All inputs are integers
* $ 1 \ le N, Q \ le 10 ^ 5 $
* $ 0 \ le A, B, S, T \ le N-1 $
* $ 0 \ le K, M \ le 10 ^ 5 $

Input

The input is given in the following format.


$ N $ $ Q $
$ A_0 $ $ B_0 $
$ A_1 $ $ B_1 $
::
$ A_ {N-2} $ $ B_ {N-2} $
$ COM_0 $
$ COM_1 $
::
$ COM_ {Q-1} $


The number of nodes in the tree $ N $ and the number of queries $ Q $ are given in the $ 1 $ row. Then the $ N-1 $ line is given information about the edges of the tree. $ A_i $, $ B_i $ indicate that there is an edge directly between the nodes $ A_i $ and $ B_i $. After that, $ Q $ instructions $ COM_j $ are given.


The format of $ COM_j $ is as follows.


$ 0 $ $ S $ $ T $


$ S $ and $ T $ are vertex numbers. The interval is specified by two nodes. This is the interval in which the shortest route from $ S $ to $ T $ is specified. Report the sum of the points written on the nodes included in the interval. However, $ S $ and $ T $ are also included in the interval. The answer can be very large, so print out the remainder divided by $ 10 ^ 9 + 7 $.



$ 1 $ $ S $ $ T $ $ K $ $ M $


As above, add points to the nodes included in the interval specified by $ S $ and $ T $. The points to be added are calculated as follows, assuming that the shortest distance from $ S $ is $ L $.



$ K + L {\ times} M $


Output

When querying $ 0 $, the sum of the points written in the nodes included in the specified interval is output in one line.

Examples

Input

3 3
0 2
1 2
1 1 0 0 1
0 0 2
0 0 1


Output

3
3


Input

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


Output

4
10
43

Solution (in CPP):

Solution:
#include <limits>
#include <stack>
#include <algorithm>
#include <string>
#include <vector>
#include <functional>
#include <iostream>
#include <queue>
#include <iterator>
#include <cstdint>
#include <utility>
#include <type_traits>
#include <cstddef>
namespace loquat {
template <int MOD>
class modulus_integer {
public:
	typedef modulus_integer<MOD> self_type;
private:
	int m_value;
	static self_type unsafe_construct(int x) noexcept {
		self_type y;
		y.m_value = x;
		return y;
	}
public:
	modulus_integer() noexcept
		: m_value(0)
	{ }
	modulus_integer(int x) noexcept
		: m_value(x % MOD)
	{
		if(m_value < 0){ m_value += MOD; }
	}
	int operator*() const noexcept { return m_value; }
	self_type& operator=(const self_type& x) noexcept {
		m_value = x.m_value;
		return *this;
	}
	self_type operator-() const noexcept {
		return unsafe_construct(m_value > 0 ? MOD - m_value : 0);
	}
	self_type operator+(const self_type& x) const noexcept {
		const int y = m_value + x.m_value;
		return unsafe_construct(y >= MOD ? y - MOD : y);
	}
	self_type operator*(const self_type& x) const noexcept {
		return unsafe_construct(
			static_cast<long long>(m_value) * x.m_value % MOD);
	}
};
template <int MOD>
inline std::ostream& operator<<(
	std::ostream& os, const modulus_integer<MOD>& x)
{
	os << *x;
	return os;
}
}
namespace loquat {
namespace bitmanip {
template <typename T>
inline auto clz(T x) noexcept ->
	typename std::enable_if<sizeof(int) < sizeof(T), unsigned int>::type
{
	return __builtin_clzll(x);
}
template <typename T>
inline T clp2(T x) noexcept {
	if(x == 0u){ return 0u; }
	return T(1u) << (sizeof(T) * 8u - clz(x - 1));
}
}
}
namespace loquat {
template <typename Impl>
class lazy_range_query_behavior_wrapper {
public:
	using value_type = typename Impl::value_type;
	using modifier_type = typename Impl::modifier_type;
private:
	template <typename T>
	struct no_reverse_value {
	private:
		static std::true_type check_unary(...);
		static std::true_type check_binary(...);
	public:
		static const bool value =
			decltype(check_unary(std::declval<T>()))::value &&
			decltype(check_binary(std::declval<T>()))::value;
	};
	Impl m_impl;
	template <typename T>
	static auto split_modifier_helper(
		const T& impl, const modifier_type& m, size_t k)
		-> decltype(impl.split_modifier(m, k))
	{
		return impl.split_modifier(m, k);
	}
	template <typename T>
	static auto modify_helper(
		const T& impl, size_t n, const value_type& v, const modifier_type& m)
		-> decltype(impl.modify(n, v, m))
	{
		return impl.modify(n, v, m);
	}
	template <typename T>
	static auto reverse_value_helper(const T&, size_t, const value_type& x)
		-> typename std::enable_if<no_reverse_value<T>::value, value_type>::type
	{
		return x;
	}
	template <typename T>
	static auto reverse_modifier_helper(const T& impl, size_t n, const modifier_type& m)
		-> decltype(impl.reverse_modifier(n, m))
	{
		return impl.reverse_modifier(n, m);
	}
public:
	lazy_range_query_behavior_wrapper(Impl impl) : m_impl(std::move(impl)) { }
	value_type identity_value() const {
		return m_impl.identity_value();
	}
	modifier_type identity_modifier() const {
		return m_impl.identity_modifier();
	}
	std::pair<modifier_type, modifier_type>
	split_modifier(const modifier_type& m, size_t k) const {
		return split_modifier_helper(m_impl, m, k);
	}
	modifier_type merge_modifier(
		const modifier_type& a, const modifier_type& b) const
	{
		return m_impl.merge_modifier(a, b);
	}
	value_type merge_value(
		const value_type& a, const value_type& b) const
	{
		return m_impl.merge_value(a, b);
	}
	value_type modify(size_t n, const value_type& v, const modifier_type& m) const {
		return modify_helper(m_impl, n, v, m);
	}
	value_type reverse_value(size_t n, const value_type& m) const {
		return reverse_value_helper(m_impl, n, m);
	}
	modifier_type reverse_modifier(size_t n, const modifier_type& m) const {
		return reverse_modifier_helper(m_impl, n, m);
	}
};
}
namespace loquat {
template <typename Behavior>
class lazy_segment_tree {
public:
	using behavior_type = Behavior;
	using value_type = typename behavior_type::value_type;
	using modifier_type = typename behavior_type::modifier_type;
private:
	size_t m_actual_size;
	std::vector<value_type> m_values;
	std::vector<modifier_type> m_modifiers;
	lazy_range_query_behavior_wrapper<behavior_type> m_behavior;
	void initialize(){
		const int n = m_values.size() / 2;
		for(int i = n - 1; i >= 0; --i){
			m_values[i] = m_behavior.merge_value(
				m_values[i * 2 + 1], m_values[i * 2 + 2]);
		}
	}
	value_type modify(
		size_t a, size_t b, size_t k, size_t l, size_t r,
		const modifier_type& modifier)
	{
		if(r <= a || b <= l){
			return m_behavior.modify(r - l, m_values[k], m_modifiers[k]);
		}else if(a <= l && r <= b){
			m_modifiers[k] =
				m_behavior.merge_modifier(m_modifiers[k], modifier);
			return m_behavior.modify(r - l, m_values[k], m_modifiers[k]);
		}
		const size_t c = l + (r - l) / 2;
		const size_t lk = k * 2 + 1, rk = lk + 1;
		const auto mp = m_behavior.split_modifier(m_modifiers[k], c - l);
		m_modifiers[k] = m_behavior.identity_modifier();
		modify(l, c, lk, l, c, mp.first);
		modify(c, r, rk, c, r, mp.second);
		const auto mq = (a < c)
			? m_behavior.split_modifier(modifier, c - std::max(a, l))
			: std::make_pair(m_behavior.identity_modifier(), modifier);
		const auto vl = modify(a, b, lk, l, c, mq.first);
		const auto vr = modify(a, b, rk, c, r, mq.second);
		m_values[k] = m_behavior.merge_value(vl, vr);
		return m_values[k];
	}
	value_type query(size_t a, size_t b, size_t k, size_t l, size_t r){
		if(r <= a || b <= l){
			return m_behavior.identity_value();
		}else if(a <= l && r <= b){
			return m_behavior.modify(r - l, m_values[k], m_modifiers[k]);
		}
		const size_t c = l + (r - l) / 2;
		const size_t lk = k * 2 + 1, rk = k * 2 + 2;
		const auto mp = m_behavior.split_modifier(m_modifiers[k], c - l);
		m_values[k] = m_behavior.modify(r - l, m_values[k], m_modifiers[k]);
		m_modifiers[k] = m_behavior.identity_modifier();
		modify(l, c, lk, l, c, mp.first);
		modify(c, r, rk, c, r, mp.second);
		const auto vl = query(a, b, lk, l, c);
		const auto vr = query(a, b, rk, c, r);
		return m_behavior.merge_value(vl, vr);
	}
public:
	lazy_segment_tree(
		size_t size,
		const behavior_type& behavior = behavior_type())
		: m_actual_size(size)
		, m_values(bitmanip::clp2(size) * 2 - 1, behavior.identity_value())
		, m_modifiers(m_values.size(), behavior.identity_modifier())
		, m_behavior(behavior)
	{
		initialize();
	}
	void modify(size_t left, size_t right, const modifier_type& modifier){
		const auto clp2_n = (m_values.size() + 1) / 2;
		modify(left, right, 0, 0, clp2_n, modifier);
	}
	value_type query(size_t left, size_t right){
		const auto clp2_n = (m_values.size() + 1) / 2;
		return query(left, right, 0, 0, clp2_n);
	}
};
}
namespace loquat {
using vertex_t = size_t;
}
namespace loquat {
namespace edge_param {
struct to_ {
	vertex_t to;
	explicit to_(vertex_t t = 0)
		: to(t)
	{ }
};
}
namespace detail {
template <typename T, typename... Params>
struct edge_param_wrapper : public T, edge_param_wrapper<Params...> {
};
template <typename T>
struct edge_param_wrapper<T> : public T {
	template <typename U>
	explicit edge_param_wrapper(U&& x)
		: T(std::forward<U>(x))
	{ }
};
}
template <typename... Params>
struct edge : public detail::edge_param_wrapper<edge_param::to_, Params...> {
	template <typename... Args>
	explicit edge(Args&&... args)
		: detail::edge_param_wrapper<edge_param::to_, Params...>(
			std::forward<Args>(args)...)
	{ }
};
}
namespace loquat {
template <typename EdgeType>
class adjacency_list {
public:
	using edge_type = EdgeType;
	using edge_list = std::vector<edge_type>;
private:
	std::vector<std::vector<EdgeType>> m_edges;
public:
	explicit adjacency_list(size_t n)
		: m_edges(n)
	{ }
	size_t size() const {
		return m_edges.size();
	}
	const edge_list& operator[](vertex_t u) const {
		return m_edges[u];
	}
	template <typename... Args>
	void add_edge(vertex_t from, Args&&... args){
		m_edges[from].emplace_back(std::forward<Args>(args)...);
	}
};
}
namespace loquat {
template <typename EdgeType, typename F>
void breadth_first_search(
	const adjacency_list<EdgeType>& g,
	vertex_t root,
	std::vector<bool>& vis,
	F func)
{
	std::queue<vertex_t> q;
	q.push(root);
	vis[root] = true;
	while(!q.empty()){
		const auto u = q.front();
		q.pop();
		for(const auto& e : g[u]){
			const auto v = e.to;
			if(vis[v]){ continue; }
			func(u, e);
			vis[v] = true;
			q.push(v);
		}
	}
}
template <typename EdgeType, typename F>
void breadth_first_search(
	const adjacency_list<EdgeType>& g,
	vertex_t root,
	F func)
{
	std::vector<bool> vis(g.size());
	breadth_first_search(g, root, vis, func);
}
}
namespace loquat {
template <typename EdgeType>
std::vector<size_t> compute_subtree_sizes(
	const adjacency_list<EdgeType>& g,
	vertex_t root)
{
	const size_t n = g.size();
	std::vector<vertex_t> order;
	order.reserve(n);
	order.push_back(root);
	breadth_first_search(g, root, [&order](vertex_t, const EdgeType& e){
		order.push_back(e.to);
	});
	std::vector<size_t> result(n);
	std::reverse(order.begin(), order.end());
	for(const auto u : order){
		size_t sum = 1;
		for(const auto& e : g[u]){
			sum += result[e.to];
		}
		result[u] = sum;
	}
	return result;
}
}
namespace loquat {
class heavy_light_decomposition {
public:
	using index_type = size_t;
	struct segment {
		index_type path_id;
		index_type first;
		index_type last;
		segment(index_type p, index_type f, index_type l)
			: path_id(p), first(f), last(l)
		{ }
	};
private:
	struct path {
		vertex_t parent;
		size_t rank;
		std::vector<vertex_t> vertices;
	};
	std::vector<path> m_paths;
	std::vector<index_type> m_vertex2path;
	std::vector<index_type> m_vertex2index;
public:
	template <typename EdgeType>
	explicit heavy_light_decomposition(
		const adjacency_list<EdgeType>& graph,
		vertex_t root = 0)
		: m_paths()
		, m_vertex2path(graph.size())
		, m_vertex2index(graph.size())
	{
		struct frame_type {
			vertex_t u;
			vertex_t p;
			frame_type() : u(0), p(0) { }
			frame_type(vertex_t u, vertex_t p) : u(u), p(p) { }
		};
		const vertex_t nil = std::numeric_limits<vertex_t>::max();
		const auto subtree_sizes = compute_subtree_sizes(graph, root);
		std::stack<frame_type> frame_stack;
		frame_stack.emplace(root, nil);
		while(!frame_stack.empty()){
			const auto f = frame_stack.top();
			frame_stack.pop();
			const index_type path_id = m_paths.size();
			path p;
			p.parent = f.p;
			p.rank = (f.p != nil ? m_paths[m_vertex2path[f.p]].rank + 1 : 0);
			vertex_t cur = f.u;
			while(cur != nil){
				const auto ss = subtree_sizes[cur];
				const auto threshold = ss / 2;
				m_vertex2path[cur] = path_id;
				m_vertex2index[cur] = p.vertices.size();
				p.vertices.push_back(cur);
				vertex_t heavy_edge = nil;
				for(const auto& e : graph[cur]){
					const auto v = e.to;
					if(subtree_sizes[v] > subtree_sizes[cur]){ continue; }
					if(heavy_edge == nil && subtree_sizes[v] >= threshold){
						heavy_edge = v;
					}else{
						frame_stack.emplace(v, cur);
					}
				}
				cur = heavy_edge;
			}
			m_paths.push_back(p);
		}
	}
	size_t count_heavy_paths() const {
		return m_paths.size();
	}
	size_t path_length(index_type p) const {
		return m_paths[p].vertices.size();
	}
	index_type path_id(vertex_t v) const {
		return m_vertex2path[v];
	}
	index_type local_index(vertex_t v) const {
		return m_vertex2index[v];
	}
	std::vector<segment> shortest_path(vertex_t s, vertex_t t) const {
		std::vector<segment> s_segments, t_segments;
		index_type s_path = path_id(s), s_index = local_index(s);
		index_type t_path = path_id(t), t_index = local_index(t);
		while(s_path != t_path){
			const size_t s_rank = m_paths[s_path].rank;
			const size_t t_rank = m_paths[t_path].rank;
			if(s_rank >= t_rank){
				const auto parent = m_paths[s_path].parent;
				s_segments.push_back(segment(s_path, s_index, 0));
				s_path  = path_id(parent);
				s_index = local_index(parent);
			}
			if(t_rank >= s_rank){
				const auto parent = m_paths[t_path].parent;
				t_segments.push_back(segment(t_path, 0, t_index));
				t_path  = path_id(parent);
				t_index = local_index(parent);
			}
		}
		std::vector<segment> result(s_segments);
		result.emplace_back(s_path, s_index, t_index);
		std::reverse(t_segments.begin(), t_segments.end());
		for(const auto& s : t_segments){ result.push_back(s); }
		return result;
	}
};
template <typename RangeQueryable>
class lazy_vertex_path_queryable_tree {
public:
	using range_queryable_type = RangeQueryable;
	using behavior_type = typename range_queryable_type::behavior_type;
	using value_type = typename behavior_type::value_type;
	using modifier_type = typename behavior_type::modifier_type;
private:
	heavy_light_decomposition m_decomposition;
	std::vector<range_queryable_type> m_range_queryables;
	lazy_range_query_behavior_wrapper<behavior_type> m_behavior;
public:
	template <typename EdgeType>
	explicit lazy_vertex_path_queryable_tree(
		const adjacency_list<EdgeType>& graph,
		vertex_t root = 0,
		const behavior_type& behavior = behavior_type())
		: m_decomposition(graph, root)
		, m_range_queryables()
		, m_behavior(behavior)
	{
		const size_t n_paths = m_decomposition.count_heavy_paths();
		m_range_queryables.reserve(n_paths);
		for(size_t i = 0; i < n_paths; ++i){
			m_range_queryables.emplace_back(
				m_decomposition.path_length(i), behavior);
		}
	}
	void modify(vertex_t s, vertex_t t, const modifier_type& m){
		const auto shortest_path = m_decomposition.shortest_path(s, t);
		modifier_type modifier = m;
		for(const auto& s : shortest_path){
			const auto path_id = s.path_id;
			const auto lo = std::min(s.first, s.last);
			const auto hi = std::max(s.first, s.last) + 1;
			const auto modifier_pair =
				m_behavior.split_modifier(modifier, hi - lo);
			const auto head_modifier = s.first > s.last
				? m_behavior.reverse_modifier(hi - lo, modifier_pair.first)
				: modifier_pair.first;
			m_range_queryables[path_id].modify(lo, hi, head_modifier);
			modifier = modifier_pair.second;
		}
	}
	value_type query(vertex_t s, vertex_t t){
		const auto shortest_path = m_decomposition.shortest_path(s, t);
		value_type acc = m_behavior.identity_value();
		for(const auto& s : shortest_path){
			const auto path_id = s.path_id;
			const auto lo = std::min(s.first, s.last);
			const auto hi = std::max(s.first, s.last) + 1;
			const auto partial = m_range_queryables[path_id].query(lo, hi);
			const auto directed_partial = s.first > s.last
				? m_behavior.reverse_value(hi - lo, partial)
				: partial;
			acc = m_behavior.merge_value(acc, directed_partial);
		}
		return acc;
	}
};
}
using namespace std;
static const int MOD = 1000000007;
using mint = loquat::modulus_integer<MOD>;
using edge = loquat::edge<>;
struct lazy_range_query_behavior {
	using value_type = mint;
	using modifier_type = pair<mint, mint>;
	value_type identity_value() const { return 0; }
	modifier_type identity_modifier() const { return make_pair(0, 0); }
	std::pair<modifier_type, modifier_type>
	split_modifier(const modifier_type& m, size_t k) const {
		return make_pair(
			modifier_type(m.first, m.second),
			modifier_type(m.first + m.second * k, m.second));
	}
	modifier_type merge_modifier(const modifier_type& a, const modifier_type& b) const {
		return modifier_type(a.first + b.first, a.second + b.second);
	}
	value_type merge_value(const value_type& a, const value_type& b) const {
		return a + b;
	}
	value_type modify(size_t n, const value_type& v, const modifier_type& m) const {
		return v + m.first * n + m.second * (n * (n - 1) / 2);
	}
	modifier_type reverse_modifier(size_t n, const modifier_type& m) const {
		return modifier_type(m.first + m.second * (n - 1), -m.second);
	}
};
using lazy_segment_tree = loquat::lazy_segment_tree<lazy_range_query_behavior>;
int main(){
	ios_base::sync_with_stdio(false);
	int n, q;
	cin >> n >> q;
	loquat::adjacency_list<edge> g(n);
	for(int i = 1; i < n; ++i){
		int a, b;
		cin >> a >> b;
		g.add_edge(a, b);
		g.add_edge(b, a);
	}
	loquat::lazy_vertex_path_queryable_tree<lazy_segment_tree> lqt(g);
	while(q--){
		int type;
		cin >> type;
		if(type == 0){
			int s, t;
			cin >> s >> t;
			cout << lqt.query(s, t) << endl;
		}else{
			int s, t, k, m;
			cin >> s >> t >> k >> m;
			lqt.modify(s, t, make_pair(k, m));
		}
	}
	return 0;
}