K xüsusi hüceyrə#11455
Sizə n \times m ölçüsündə, xüsusi hüceyrənin vurğulandığı bir matrisa verilir. hüceyrəsindən hüceyrəsinə çatmaq lazımdır. Yalnız sağa və ya aşağıya hərəkət etməyə icazə verilir.
Hər bir xüsusi hüceyrənin müəyyən gücü var. -ci xüsusi hüceyrənin p_i gücü var və onun üzərindən keçərkən siz bu güc alırsınız.
-dən -ə qədər bütün mümkün yolları nəzərə alaraq, toplaya biləcək ümumi gücü tapmaq tələb olunur.
Qeyd edək ki:
Yolun gücü, o yolda ziyarət edilmiş bütün xüsusi hüceyrələrin p_i dəyərlərinin cəmi kimi müəyyən edilir.
Xüsusi olmayan adi hüceyrələrin gücü sıfıra bərabərdir.
Birinci sətir tam ədədini — testlərin sayını ehtiva edir.
Hər testin birinci sətirində üç tam ədəd n, m~(1 \le n, m \le 10^5) və k~(1 \le k \le 10^6) verilmişdir, burada n \times m şəbəkənin ölçüsüdür və xüsusi hüceyrələrin sayıdır.
Növbəti sətirin hər biri üç ədəd x_i, y_i~(1 \le x_i \le n, 1 \le y_i \le m) və p_i~(1 \le p_i \le 10^5) ehtiva edir, burada (x_i, y_i) xüsusi hüceyrənin koordinatlarıdır və p_i onun gücüdür.
Hər test üçün toplana biləcək ümumi gücü ayrıca bir sətirdə çıxarın. Cavab çox böyük ola biləcəyi üçün onu 10^9 + 7 modulunda çıxarın.
Nümunə 1