E. Тогтмол

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 512 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Бяцхан Икс саяхан олон гишүүнт хугацаанд #P-бүрэн бодлогыг шийдвэрлэсэн. Иймээс тэр танд энэ даалгаврыг өгч байна.

$n × n$ хэмжээтэй тусгай матриц $A$ байгаа. Та энэ матрицын тогтмолыг $1000000007 (10^{9} + 7)$-д хуваагаад гарсан үлдэгдлийг олох ёстой. Тусгай матриц гэдэг нь тухайн матрицын бүх элементийг $1$-тэй тэнцүү болгоод зөвхөн $k$ ширхэг элементийн утгыг нэмж өгсөн байхыг хэлнэ.

Та энэ холбоосоор орж матрицын тогтмолын тодорхойлолтыг харж болно: https://en.wikipedia.org/wiki/Permanent

Оролт

Эхний мөрөнд зайгаар тусгаарласан хоёр бүхэл $n, k$ ($1 ≤ n ≤ 10^{5}; 1 ≤ k ≤ 50$) тоонууд агуулагдана.

Дараагийн $k$ мөрөнд матрицын элементүүд агуулагдана. $i$-р мөрөнд зайгаар тусгаарлагдсан гурван бүхэл $x_{i}, y_{i}, w_{i}$ ($1 ≤ x_{i},  y_{i} ≤  n; 0  ≤  w_{i}  ≤ 10^{9}$) тоонууд агуулагдана. Эдгээр тоонууд нь $A_{x_{i}, y_{i}} = w_{i}$ гэдгийг илэрхийлнэ. Матрицын өгөгдсөн элементүүдээс бусад бүх элементүүд нь $1$-тэй тэнцүү байна.

Энд бүх $(x_{i}, y_{i})$ байрлалууд нь ялгаатай гэдэг нь баталгаатай юм.

Гаралт

Матрицын тогмолыг $1000000007 (10^{9}  +  7)$-д хуваагаад гарсан үлдэгдлийг хэвлэнэ.

Орчуулсан: Даариймаа

Жишээ тэстүүд

Оролт
3 1
1 1 2
Гаралт
8
Оролт
10 10
3 3 367056794
6 2 124561273
1 3 46718146
6 9 415916869
10 5 985968336
3 1 526792265
1 4 386357058
10 4 349304187
2 7 102032499
3 6 502679075
Гаралт
233333333
Сэтгэгдлүүдийг ачааллаж байна...