Background

Luogu’s testdata is only for non-official community communication and is not official testdata. Official judging link: https://www.cspro.org/.

The Xixiaifu Island operating company has recently been strongly promoting an intelligent municipal management system. This system was developed by the Xixiaifu Island Information Center. Its main purpose is to guide the maintenance and renewal of municipal facilities by carefully evaluating the condition of municipal facilities across the island. The core of this system is an intelligent sensor network, which can automatically evaluate the island’s municipal facilities. Maintaining municipal facilities requires certain costs, and municipal facilities that have been neglected for years may also cause losses to the island’s residents. To balance costs and benefits, the Information Center developed a mathematical model that describes the complex mathematical relationship among these variables and the profit/loss. To obtain the optimal cost, it is necessary to rely on the gradient descent algorithm to solve it.

In the gradient descent algorithm, computing the partial derivative of a function at a point with respect to a certain variable is very important. Little C is responsible for implementing this function, but he is still confused about the technical details and hopes you can help him complete this task.

Problem Description

Let the function to be computed be $u = f(x_1, x_2, \dots, x_n)$. This problem asks you to compute the partial derivative of $u$ with respect to $x_i$ at $(a_1, a_2, \dots, a_n)$, i.e. $\frac{\partial u}{\partial x_i}(a_1, a_2, \dots, a_n)$.

To compute the partial derivative of a multivariable function at a point with respect to one variable: treat that variable as the only variable and treat the other variables as constants, use the differentiation method for single-variable functions to obtain the expression of the partial derivative, and then substitute the coordinates of the given point.

For example, to compute the partial derivative of $u = x_1 \cdot x_1 \cdot x_2$ with respect to $x_1$ at $(1, 2)$, you can treat $x_2$ as a constant and apply differentiation formulas step by step. First apply the product rule: $(x_1 \cdot (x_1 \cdot x_2))' = x_1'(x_1 \cdot x_2) + x_1(x_1 \cdot x_2)'$; then apply the rule for multiplying a constant and a variable to get $x_1' \cdot x_1 \cdot x_2 + x_1 \cdot x_2 \cdot x_1'$; finally apply $x' = 1$ to get $1 \cdot x_1 \cdot x_2 + x_1 \cdot x_2 \cdot 1$. After simplification, $\frac{\partial u}{\partial x_1} = 2x_2 \cdot x_1$. Substituting $(1, 2)$ gives $\frac{\partial u}{\partial x_1}(1, 2) = 4$.

Common differentiation formulas include:

• $c' = 0$ ($c$ is a constant).
• $x' = 1$.
• $(u + v)' = u' + v'$.
• $(cu)' = cu'$ ($c$ is a constant).
• $(u - v)' = u' - v'$.
• $(uv)' = u'v + uv'$.

In this problem, the function $f$ you need to compute consists only of constants, variables, and their addition, subtraction, and multiplication. For easier parsing, the function expression has been converted into Reverse Polish Notation (postfix notation). For example, the Reverse Polish Notation of $x_1 \cdot x_1 \cdot x_2$ is x1 x1 * x2 *. Reverse Polish Notation is the result of a postorder traversal of the expression tree. To restore the original expression from Reverse Polish Notation, you can do the following: assume there is an empty stack $S$. Read each element of the Reverse Polish Notation in order. If it is a variable or a constant, push it into $S$; if it is an operator, pop two elements from $S$, perform the corresponding operation, and then push the result back into $S$. Finally, if there is exactly one element in $S$, the expression is valid and its value is the value of that element. For example, for x1 x1 * x2 *, reading it with the method above, the changes of stack $S$ are as follows (left is the bottom of the stack, right is the top):

1. $x_1$.
2. $x_1,\ x_1$.
3. $(x_1 \cdot x_1)$.
4. $(x_1 \cdot x_1),\ x_2$.
5. $((x_1 \cdot x_1) \cdot x_2)$.

Input Format

Read from standard input.

The first line contains two positive integers $n$ and $m$ separated by spaces, representing the number of variables in the target function and the number of partial derivatives to be computed.

The second line is a Reverse Polish Notation expression representing the function $f$. Each element is separated by a space, and each element can be:

• A variable $x_i$, written as the character x followed by a positive integer, representing the $i$-th variable, where $i = 1, 2, \dots, n$. For example, x1 represents the first variable $x_1$.
• An integer constant written in decimal, with value between $-10^5$ and $10^5$.
• An operator: + for addition, - for subtraction, * for multiplication.

From the third line to the $(m + 2)$-th line, each line contains $n + 1$ integers separated by spaces. The first integer is the index $i = 1, 2, \dots, n$ of the variable for which the partial derivative is requested, and the remaining integers are the coordinates $a_1, a_2, \dots, a_n$ of the point to be evaluated. The input guarantees that for all $i = 1, 2, \dots, n$, $a_i$ is between $-10^5$ and $10^5$.

Output Format

Output to standard output.

Output $m$ lines. Each line contains one integer, which is the corresponding partial derivative modulo $10^9 + 7$. That is, if the result is $y$ and the output is $k$, then there exists an integer $t$ such that $y = k + t \cdot (10^9 + 7)$ and $0 \le k < 10^9 + 7$.

2 2
x1 x1 x1 * x2 + *
1 2 3
2 3 4

15
3

3 5
x2 x2 * x2 * 0 + -100000 -100000 * x2 * -
3 100000 100000 100000
2 0 0 0
2 0 -1 0
2 0 1 0
2 0 100000 0

0
70
73
73
999999867

Hint

Sample 1 Explanation

Reading the Reverse Polish Notation, the expression to be differentiated is: $u = x_1 \cdot (x_1 \cdot x_1 + x_2)$, i.e. $u = x_1^3 + x_1 x_2$.

Taking the partial derivative with respect to $x_1$, we get $\frac{\partial u}{\partial x_1} = 3x_1^2 + x_2$. Substituting $(2, 3)$ gives $\frac{\partial u}{\partial x_1}(2, 3) = 15$.

Taking the partial derivative with respect to $x_2$, we get $\frac{\partial u}{\partial x_2} = x_1$. Substituting $(3, 4)$ gives $\frac{\partial u}{\partial x_2}(3, 4) = 3$.

Sample 2 Explanation

Reading the Reverse Polish Notation, the expression to be differentiated is: $u = x_2 \cdot x_2 \cdot x_2 + 0 - (-10^5) \cdot (-10^5) \cdot x_2$, i.e. $u = x_2^3 - 10^{10}x_2$.

Since $u$ actually does not contain $x_1$ and $x_3$, the results of taking partial derivatives with respect to these two variables are both $0$.

Taking the partial derivative with respect to $x_2$, we get $\frac{\partial u}{\partial x_2} = 3x_2^2 - 10^{10}$.

Subtasks

Hint

In C++, you can use std::getline(std::cin, str) to read a string until the end of the line.

When computing the modulo of an integer $n$ by $M$, if $n$ is negative, be careful to adjust the result into the interval $[0, M)$.

Translated by ChatGPT 5