Cây Đẹp

Điểm: 8,00 (OI)

Giới hạn thời gian: 2.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Cho bốn số nguyên $n$ , $m$ , $a$ , $b$ . Gọi một cây đẹp là một cây có trọng số gồm $n$ đỉnh được đánh số từ $1$ đến $n$ , có đúng $n - 1$ cạnh, trong đó mỗi cạnh có trọng số nguyên thuộc đoạn $[1, m]$ , và khoảng cách giữa hai đỉnh $a$ và $b$ trên cây bằng đúng $m$ . Khoảng cách giữa hai đỉnh là tổng trọng số các cạnh trên đường đi đơn nối chúng.

Hai cây được coi là khác nhau nếu tồn tại một cạnh (kèm trọng số) xuất hiện ở cây này nhưng không xuất hiện ở cây kia.

Hãy đếm số cây đẹp theo modulo $10^{9} + 7$ .

Dữ liệu vào

Một dòng chứa bốn số nguyên $n$ , $m$ , $a$ , $b$ .

Dữ liệu ra

Một số nguyên duy nhất — số cây đẹp theo modulo $10^{9} + 7$ .

Ràng buộc

$2 \leq n \leq 10^{6}$
$1 \leq m \leq 10^{6}$
$1 \leq a, b \leq n$
$a \neq b$

Ví dụ

Input	Output	Giải thích
3 2 1 3	5	Có $5$ cây thoả mãn khoảng cách từ đỉnh $1$ đến đỉnh $3$ bằng $2$ .
3 1 1 2	2	Có $2$ cây thoả mãn khoảng cách từ đỉnh $1$ đến đỉnh $2$ bằng $1$ .
5 15 1 5	345444	Khoảng cách từ đỉnh $1$ đến đỉnh $5$ phải bằng $15$ .

Bình luận

Không có bình luận tại thời điểm này.