409965: GYM103870 J Thomas Game Revisited Again

Thomas wants to game! But teacher is making him do some hard problems to stop him from gaming. In particular, teacher has forced Thomas to work on an $$$O(n)$$$ matrix mutliplication problem. Thomas currently has a matrix multiplication for two $$$n$$$ by $$$n$$$ matrices written as follows:

for(int i = 0; i<n; i++){
  for(int j = 0; j<n; j++){
    for(int k = 0; k<n; k++){
      c[i][j] = c[i][j] + a[i][k]*b[k][j];
    }
  }
}

Thomas's code is not $$$O(n)$$$ and TLE's! However, Thomas has thought of a way to make his matrix multiplation $$$O(1)$$$. He decided to handwrite all the transitions of his $$$n^3$$$ matrix multiplication! In particular, for all pairs $$$i,j$$$ such that $$$0 \leq i, j < n$$$, Thomas writes:

c[i][j] = a[i][0]*b[0][j] + a[i][1]*b[1][j] + ... + a[i][n-1]*b[n-1][j];

Please note that in all these examples so far, $$$a$$$, $$$b$$$, and $$$c$$$ have all been placeholders for the actual variable names Thomas uses. In practice, Thomas actually uses much more productive variable names (probably...)!

So below is an "expanded" matrix multiplication of $$$2$$$x$$$2$$$ matrices m1 and m2 into ret.

ret[0][0] = m1[0][0]*m2[0][0] + m1[0][1]*m2[1][0];
ret[1][0] = m1[1][0]*m2[0][0] + m1[1][1]*m2[1][0];
ret[0][1] = m1[0][0]*m2[0][1] + m1[0][1]*m2[1][1];
ret[1][1] = m1[1][0]*m2[0][1] + m1[1][1]*m2[1][1];

So now Thomas asks you, if you are given the length of the names of the result matrix, left matrix, and right matrix, and their dimension $$$n$$$, what is the number of non-whitespace characters in the expanded form of that matrix multiplication. Note that new lines and spaces are ignored when Thomas says "no white spaces"; all other characters contribute to the answer.

You will answer $$$T$$$ testcases $$$(1 \leq T \leq 10^5)$$$.

Each testcase consists of $$$4$$$ integers, $$$a, l, r, n$$$ $$$(1 \leq a, l, r \leq 10^3), (1 \leq n \leq 10^9)$$$. $$$a$$$ denotes the length of the name of the resulting matrix, $$$l$$$ denotes the length of the name the left hand matrix, $$$r$$$ denotes the length of the name of the right hand matrix, and $$$n$$$ is the dimension of the matrix multiplied.

Note that there are no constraints on the sum of any of the input values specified above.

Test case 1 will consist of all $$$10^4$$$ ways to pick $$$a, l, r, n$$$ from the numbers $$$1 \cdots 10$$$.

Tests $$$2-3$$$ will satsify $$$(1 \leq T \leq 10, 1 \leq n \leq 1000)$$$.

Tests $$$4 - 6$$$ will satsify $$$(1 \leq T \leq 10, 1 \leq n \leq 10^5)$$$.

Tests $$$7 - 10$$$ will satsify $$$(1 \leq T \leq 10^5, 1 \leq n \leq 10^5)$$$.

There are no additional constraints for the remaining tests.

Output $$$T$$$ lines, each line containing one integer, the number of characters in the Thomas expanded matrix multiplication. Since this number may be very large, please find it modulo $$$10^9 + 7$$$.

3
1 1 1 2
1 2 3 4
3 3 6 6

160
1344
5328

2
366 366 336 336
1000 1000 1000 33663366

456345987
778866085

—

Idea: 3366

Preparation: 3366

Occurrences: Novice 8, Intermediate 6