题目描述

小 Q 在学校里非常调皮。

他上课时总是很无聊，他总是把课堂弄得一团糟。老师希望让他冷静下来，所以给他出了一道很难的数学题。

老师给小 Q 一个算术表达式 $A$、整数 $P$ 和 $M$，小 Q 要回答的是以下问题：

求最小非负整数 $x$，使含 $x$ 的表达式 $A$ 除以 $M$ 余数等于 $P$。

注意每一个运算符均会连接两个数或是变量。每一个乘号都不会省略且不允许连接两个含有 $x$ 的表达式。括号均合法，可能存在括号内容仅有一个数或变量的情况。

题目保证原表达式化简后一定能写成一个形如 $kx+b$ 的一元一次式。

输入格式

第一行，一行表达式 $A$。

第二行，两个正整数 $P, M$。

输出格式

第一行，一个正整数 $x$。

5+3+x
9 10

1

20+3+x
0 5

2

提示

数据规模及约定

对于 $100\%$ 的数据：

• 令 $|A|$ 为字符串 $A$ 的长度，那么 $1 \le |A| \le 10 ^ 5$。
• 表达式 $A$ 中仅会有 $\texttt{+}$，$\texttt{-}$，$\texttt{*}$，$\texttt{(}$，$\texttt{)}$，$\texttt{x}$，和 $\texttt{0}$ $\sim$ $\texttt{9}$。
• $0 \le P \le M - 1$。
• $1 \le M \le 10 ^ 6$。

说明

翻译自 COCI 2015-2016 #3 D SLON，满分 120。