k спеціальних клітин#11455
Вам дана матриця розміром n \times m, в якій виділені спеціальних клітин. Необхідно дістатися з клітинки до клітинки . Дозволено рухатися лише вправо або вниз.
Кожна з спеціальних клітин має певну силу. -та спеціальна клітинка має силу p_i, і при проходженні через неї ви отримуєте цю силу.
Потрібно знайти сумарну силу, яку можна набрати, розглядаючи всі можливі шляхи від до .
Зазначимо, що:
Сила шляху визначається як сума значень p_i всіх спеціальних клітин, відвіданих на цьому шляху.
Звичайні клітини, які не є спеціальними, мають силу, що дорівнює нулю.
Перший рядок містить ціле число — кількість тестів.
У першому рядку кожного тесту задано три цілі числа n, m~(1 \le n, m \le 10^5) і k~(1 \le k \le 10^6), де n \times m — розмір сітки, а — кількість спеціальних клітин.
Кожен з наступних рядків містить три числа x_i, y_i~(1 \le x_i \le n, 1 \le y_i \le m) і p_i~(1 \le p_i \le 10^5), де (x_i, y_i) — координати спеціальної клітини, а p_i — її сила.
Для кожного тесту виведіть в окремому рядку сумарну силу, яку можна набрати. Оскільки відповідь може бути дуже великою, виведіть її за модулем 10^9 + 7.
Приклад 1