Задачі
K специальных ячеек
K специальных ячеек
Вам дана матрица, в которой выделены $k$ специальных ячеек. Вы должны достичь клетку $(n, m)$ из $(1, 1)$. Из любой клетки можно двигаться только вправо или вниз.
$k\:$ специальных ячеек --- это те ячейки сетки, которые обладают особой силой. $i$-я специальная ячейка имеет $p_i$ единиц силы, и если Вы проходите по этой ячейке, то приобретаете эту силу.
Найдите общую суммарную силу, которую Вы можете приобрести после прохождения всех возможных путей в сетке, чтобы достичь ячейки $(n, m)$.
Отметим, что:
\begin{itemize}
\item Сила пути равна сумме сил $p_i$ всех специальных ячеек, посещенных на этом пути.
\item Ячейки, не являющиеся специальными, имеют силу ноль.
\end{itemize}
\InputFile
Первая строка содержит количество тестов $t$.
Первая строка каждого теста содержит три целых числа $n, m\:(1 \le n, m \le 10^5)$ и $k\:(1 \le k \le 10^6)$, где $n * m$ --- размер сетки, а $k$ --- общее количество специальных ячеек в сетке. Каждая из следующих $k$ строк содержит $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$ --- ее сила.
\OutputFile
Для каждого теста выведите в отдельной строке общую силу, которую Вы можете приобрести. Поскольку общая сила может быть слишком большой, то выведите ее по модулю $10^9 + 7$.
Вхідні дані #1
1 2 2 2 1 2 4 2 1 7
Вихідні дані #1
11