#216067. [CSPro 31] 梯度求解

洛谷的测试数据仅供民间交流使用，非官方测试数据。官方评测链接：https://www.cspro.org/。

西西艾弗岛运营公司近期在大力推广智能化市政管理系统。这套系统是由西西艾弗岛信息中心研发的。它的主要目的是，通过详细评估岛上各处的市政设施的状况，来指导市政设施的维护和更新。这套系统的核心是一套智能化的传感器网络，它能够自动地对岛上的市政设施进行评估。对市政设施的维护是需要一定成本的，而年久失修的市政设施也可能给岛上的居民造成损失。为了能够平衡成本和收益，信息中心研发了一款数学模型，描述这些变量和损益之间的复杂数学关系。要想得到最优化的成本，就要依靠梯度下降算法来求解。

梯度下降算法中，求解函数在一点处对某一自变量的偏导数是十分重要的。小 C 负责实现这个功能，但是具体的技术实现，他还是一头雾水，希望你来帮助他完成这个任务。

设被求算的函数 ，本题目要求你求出 对 在 处的偏导数 。

求算多元函数在一点处对某一自变量的偏导数的方法是：将函数的该自变量视为单一自变量，其余自变量认为是常数，运用一元函数求导的方法求出该偏导数表达式，再代入被求算的点的坐标即可。

例如，要求算 对 在 处的偏导数，可以将 视为常数，依次应用求导公式。先应用乘法的求导公式：；再应用常数与变量相乘的求导公式，得到 ；最后应用公式 得到 。整理得 。再代入 得到 。

常见的求导公式有：

• （ 是常数）
• （ 是常数）

本题目中，你需要求解的函数 仅由常数、自变量和它们的加法、减法、乘法组成。且为程序识读方便，函数表达式已经被整理为逆波兰式（后缀表达式）的形式。例如， 的逆波兰式为 x1 x1 * x2 *。逆波兰式即为表达式树的后序遍历的结果。若要从逆波兰式还原原始计算算式，可以按照这一方法进行：假设存在一个空栈 ，依次读取逆波兰式的每一个元素，若读取到的是变量或常量，则将其压入 中；若读取到的是计算符号，则从 中取出两个元素，进行相应运算，再将结果压入 中。最后，若 中存在唯一的元素，则该表达式合法，其值即为该元素的值。例如对于逆波兰式 x1 x1 * x2 *，按上述方法读取，栈 的变化情况依次为（左侧是栈底，右侧是栈顶）：

1. ；
2. ；
3. ；
4. ；
5. 。

从标准输入读入数据。

输入的第一行是由空格分隔的两个正整数 、，分别表示要求解函数中所含自变量的个数和要求解的偏导数的个数。

输入的第二行是一个逆波兰式，表示要求解的函数 。其中，每个元素用一个空格分隔，每个元素可能是：

• 一个自变量 ，用字符 x 后接一个正整数表示，表示第 个自变量，其中 。例如，x1 表示第一个自变量 。
• 一个整常数，用十进制整数表示，其值在 到 之间。
• 一个运算符，用 + 表示加法，- 表示减法，* 表示乘法。

输入的第三行到第 行，每行有 个用空格分隔的整数。其中第一个整数是要求偏导数的自变量的编号 ，随后的整数是要求算的点的坐标 。输入数据保证，对于所有的 ， 都在 到 之间。

输出到标准输出。

输出 行，每行一个整数，表示对应的偏导数对 取模的结果。即若结果为 ，输出为 ，则保证存在整数 ，满足 且 。

样例输入 1

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

样例输出 1

15
3

样例输入 2

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

样例输出 2

0
70
73
73
999999867

样例 1 解释

读取逆波兰式，可得被求导的式子是：，即 。

对 求偏导得 。代入 得到 。

对 求偏导得 。代入 得到 。

样例 2 解释

读取逆波兰式，可得被求导的式子是：，即 。

因为 中实际上不含 和 ，对这两者求偏导结果均为 。

对 求偏导得 。

子任务

提示

C++ 中可以使用 std::getline(std::cin, str) 读入字符串直到行尾。

当计算整数 对 的模时，若 为负数，需要注意将结果调整至区间 内。