背景
西西艾弗島運營公司近期在大力推廣智能化市政管理系統。這套系統是由西西艾弗島信息中心研發的。它的主要目的是，通過詳細評估島上各處的市政設施的狀況，來指導市政設施的維護和更新。這套系統的核心是一套智能化的傳感器網絡，它能夠自動地對島上的市政設施進行評估。對市政設施的維護是需要一定成本的，而年久失修的市政設施也可能給島上的居民造成損失。為了能夠平衡成本和收益，信息中心研發了一款數學模型，描述這些變量和損益之間的復雜數學關系。要想得到最優化的成本，就要依靠梯度下降算法來求解。

梯度下降算法中，求解函數在一點處對某一自變量的偏導數是十分重要的。小 C 負責實現這個功能，但是具體的技術實現，他還是一頭霧水，希望你來幫助他完成這個任務。

問題描述
設被求算的函數 u=f(x1,x2,…,xn)，本題目要求你求出 u 對 xi 在 (a1,a2,…,an) 處的偏導數 ?u?xi(a1,a2,…,an)。

求算多元函數在一點處對某一自變量的偏導數的方法是：將函數的該自變量視為單一自變量，其余自變量認為是常數，運用一元函數求導的方法求出該偏導數表達式，再代入被求算的點的坐標即可。

例如，要求算 u=x1?x1?x2 對 x1 在 (1,2) 處的偏導數，可以將 x2 視為常數，依次應用求導公式。先應用乘法的求導公式：(x1?(x1?x2))′=x1′(x1?x2)+x1(x1?x2)′；再應用常數與變量相乘的求導公式，得到 x1′?x1?x2+x1?x2?x1′；最后應用公式 x′=1 得到 1?x1?x2+x1?x2?1。整理得 ?u?x1=2x2?x1。再代入 (1,2) 得到 ?u?x1(1,2)=4。

常見的求導公式有：

（是常數）c′=0 （c是常數）
x′=1
(u+v)′=u′+v′
（是常數）(cu)′=cu′ （c是常數）
(u?v)′=u′?v′
(uv)′=u′v+uv′
本題目中，你需要求解的函數 f 僅由常數、自變量和它們的加法、減法、乘法組成。且為程序識讀方便，函數表達式已經被整理為逆波蘭式（后綴表達式）的形式。例如，x1?x1?x2 的逆波蘭式為 x1 x1 * x2 *。逆波蘭式即為表達式樹的后序遍歷的結果。若要從逆波蘭式還原原始計算算式，可以按照這一方法進行：假設存在一個空棧 S，依次讀取逆波蘭式的每一個元素，若讀取到的是變量或常量，則將其壓入 S 中；若讀取到的是計算符號，則從 S 中取出兩個元素，進行相應運算，再將結果壓入 S 中。最后，若 S 中存在唯一的元素，則該表達式合法，其值即為該元素的值。例如對于逆波蘭式 x1 x1 * x2 *，按上述方法讀取，棧 S 的變化情況依次為（左側是棧底，右側是棧頂）：

x1；
x1，x1；
(x1?x1)；
(x1?x1)，x2；
((x1?x1)?x2)。
輸入格式
從標準輸入讀入數據。

輸入的第一行是由空格分隔的兩個正整數 n、m，分別表示要求解函數中所含自變量的個數和要求解的偏導數的個數。

輸入的第二行是一個逆波蘭式，表示要求解的函數 f。其中，每個元素用一個空格分隔，每個元素可能是：

一個自變量 xi，用字符 x 后接一個正整數表示，表示第 i 個自變量，其中 i=1,2,…,n。例如，x1 表示第一個自變量 x1。
一個整常數，用十進制整數表示，其值在 ?105 到 105 之間。
一個運算符，用 + 表示加法，- 表示減法，* 表示乘法。
輸入的第三行到第 m+2 行，每行有 n+1 個用空格分隔的整數。其中第一個整數是要求偏導數的自變量的編號 i=1,2,…,n，隨后的整數是要求算的點的坐標 a1,a2,…,an。
輸入數據保證，對于所有的 i=1,2,…,n，ai 都在 ?105 到 105 之間。

輸出格式
輸出到標準輸出中。

輸出 m 行，每行一個整數，表示對應的偏導數對 109+7 取模的結果。即若結果為 y，輸出為 k，則保證存在整數 t，滿足 y=k+t?(109+7) 且 0≤k<109+7。

樣例 1 輸入
2 2
x1 x1 x1 * x2 + *
1 2 3
2 3 4

樣例 1 輸出
15
3

樣例 1 說明
讀取逆波蘭式，可得被求導的式子是：u=x1?(x1?x1+x2)，即 u=x13+x1x2。

對 x1 求偏導得 ?u?x1=3x12+x2。代入 (2,3) 得到 ?u?x1(2,3)=15。

對 x2 求偏導得 ?u?x2=x1。代入 (3,4) 得到 ?u?x2(3,4)=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

樣例 2 說明
讀取逆波蘭式，可得被求導的式子是：u=x2?x2?x2+0?(?105)?(?105)?x2，即 u=x23?1010x2。

因為 u 中實際上不含 x1 和 x3，對這兩者求偏導結果均為 0。

對 x2 求偏導得 ?u?x2=3x22?1010。

評測用例規模與約定
測試點?? ?n?? ?m?? ?表達式的性質
1, 2?? ?=1?? ?≤100?? ?僅含有 1 個元素
3, 4?? ?=1?? ?≤100?? ?僅含有一個運算符
5, 6?? ?≤10?? ?≤100?? ?含有不超過 120 個元素，且不含乘法
7, 8?? ?≤10?? ?≤100?? ?含有不超過 120 個元素
9, 10?? ?≤100?? ?≤100?? ?含有不超過 120 個元素
提示
C++ 中可以使用 std::getline(std::cin, str) 讀入字符串直到行尾。

當計算整數 n 對 M 的模時，若 n 為負數，需要注意將結果調整至區間 [0,M) 內。