Bạn biết rằng lâu đài hắc ám có căn phòng, lối đi hai chiều có thể xây dựng, cùng với độ dài của mỗi lối đi. Lâu đài có dạng hình cây và thỏa mãn các điều kiện sau:
Gọi là độ dài đường đi ngắn nhất từ phòng số đến phòng số nếu tất cả các lối đi đều được xây dựng.
Gọi là độ dài đường đi từ phòng số đến phòng số trong lâu đài hình cây thực tế được xây dựng.
Yêu cầu với mọi số nguyên (), ta có .
Bạn muốn biết có bao nhiêu phương án xây dựng lâu đài khác nhau. Tất nhiên, bạn chỉ cần xuất kết quả sau khi lấy phần dư cho .
Dữ liệu:
Dòng đầu tiên là hai số nguyên cách nhau bởi dấu cách .
Từ dòng thứ 2 đến dòng thứ , mỗi dòng gồm 3 số nguyên cách nhau bởi dấu cách : biểu thị độ dài lối đi giữa phòng và phòng là .
Kết quả:
Một số nguyên: số lượng phương án xây dựng lâu đài khác nhau sau khi lấy phần dư cho .
