All Tracks Math Combinatorics Basics of Combinatorics Problem

K-Special Cells

Basics of Combinatorics, Combinatorics, Easy, Math



  • You are given a \(N \times M\) matrix which has K special cells in it. You have to reach \((N, M)\) from \((1, 1)\). From any cell, you can only move rightwards or downwards.
  • The \(K-special\) cells are those cells in this grid which have special strength at them. \(i^{th}\) special cell has \(P[i]\) units of strength and if you travel through this cell, you store the strength.
  • Find the total strength you can store after travelling through all the possible paths in the grid to reach cell \((N,M)\).

  • Note:
    1. The strength of a path is the sum of strength \(P[i]\) of all the special cells that are visited in this path.
    2. The cells that are not special have power quotient equals to zero.


Input format

  • The first line contains the total number of test cases denoted by T.
  • The first line of each test case contains three space separated integers N, M and K where N x M is the size of grid and K is the total number of special cells in the grid.
  • Each of next K lines contains X[i], Y[i], and P[i] where (X[i],Y[i]) is the location of special cell and P[i] is the cell strength.



Output format

  • For each test case, print in a new line a single integer representing the total strength that you can store, as the total strength can be too large, print it modulo \(10^9+7\).



  • \(1 \le T \le 3\)
  • \(1 \le N, M, P[i] \le 10^5\)
  • \(1 \le X[i] \le N\)
  • \(1 \le Y[i] \le M\)
  • \(1 \le K \le 10^6\)


2 2 2
1 2 4
2 1 7

Total Power that can be collected is 11, as there are only two possible paths in grid of size 2x2 and total power we can collect by traveling through both of these paths is 11.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: Bash, C, C++, C++14, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Julia, Kotlin, Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Swift, Swift-4.1, TypeScript, Visual Basic


Initializing Code Editor...
Your Rating:


This Problem was Asked in

Redlock India Pvt. Ltd.

Challenge Name

Redlock Developer Hiring Challenge

  • Data Structures > Advanced Data Structures
  • Data Structures > Advanced Data Structures
View All Notifications