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 \lt 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