K спеціальних комірок

Вам надано матрицю, в якій виділено $k$ спеціальних комірок. Ваше завдання — дістатися до клітинки $(n,m)$, починаючи з $(1,1)$. З будь-якої клітинки можна рухатися лише вправо або вниз.

$k$ спеціальних комірок — це ті комірки сітки, що мають особливу силу. $i$-та спеціальна комірка має силу $p_i$, і якщо ви проходите через цю комірку, ви отримуєте цю силу.

Визначте загальну сумарну силу, яку ви можете отримати, пройшовши всі можливі шляхи в сітці, щоб досягти клітинки $(n,m)$.

Зверніть увагу, що:

• Сила шляху дорівнює сумі сил $p_i$ всіх спеціальних комірок, відвіданих на цьому шляху.

• Комірки, які не є спеціальними, мають силу нуль.

Вхідні дані

Перший рядок містить кількість тестів $t$.

Перший рядок кожного тесту містить три цілі числа $n,m(1\le n,m\le 10^5)$ і $k(1\le k\le 10^6)$, де $n\ast 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$ — її сила.

Вихідні дані

Для кожного тесту виведіть в окремому рядку загальну силу, яку ви можете отримати. Оскільки загальна сила може бути дуже великою, виведіть її за модулем $10^9+7$.

Приклади