|
||||||||||
Add or Multiply 1Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)Total Submission(s): 570 Accepted Submission(s): 222 Problem Description 前两段和第五题相同,但你不需要阅读第五题就可以完成这个题目。 你有一个数字 $x$ 和若干个操作,每个操作是 $+a_i$ 或者乘 $\times a_i$ 中的一种。你可以重新排列这些操作的顺序,然后对数字 $x$ 执行这些操作。 比如说三个操作是 $+a_1, +a_2, \times a_3$。如果按顺序执行这三个操作,那么得到的结果是 $((x+a_1)+a_2) \times a_3$。如果排列成 $+a_2, \times a_3, +a_1$,那么得到的结果是 $((x+a_2)\times a_3)+a_1$。 我们会发现,有一些操作顺序计算出来的结果是本质相同的,比如说$+a_1, +a_2, \times a_3$和$+a_2, +a_1, \times a_3$这样运算下来结果是一样的。我们认为两个操作顺序计算的结果本质相同,当且仅当无论代入什么数,计算出来的结果都是一样的。 请问有多少种本质不同的操作序列。换句话说就是最多能找到多少个操作序列,使得这些操作序列任意两个都不是本质相同的。由于答案很大,输出对$10^9+7$取模的结果。 在这个题目中,我们只会给出加法操作和乘法操作的个数,分别是$n, m$,并不会给出具体的顺序和数字。容易发现,答案与具体的顺序和数字无关。 Input 本题有多组测试数据。 第一行一个整数 $T(1 \leq T \leq 10^4)$ 表示数据组数。 对于每组数据,一行两个整数 $n, m (1 \leq n, m \leq 3000)$ 描述一组询问,表示操作中加法个数和乘法个数。 Output 对于每组数据输出一行,表示答案。 Sample Input
Sample Output
Source | ||||||||||
|