F.A.Q
Hand In Hand
Online Acmers
Problem Archive
Realtime Judge Status
Authors Ranklist
 
     C/C++/Java Exams     
ACM Steps
Go to Job
Contest LiveCast
ICPC@China
Best Coder beta
VIP | STD Contests
    DIY | Web-DIY beta
Author ID 
Password 
 Register new ID

Add or Multiply 1

Time 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
3 2 1 5 5 100 100
 

Sample Output
4 329462 294770659
 

Source
 

Statistic | Submit | Discuss | Note
Hangzhou Dianzi University Online Judge 3.0
Copyright © 2005-2024 HDU ACM Team. All Rights Reserved.
Designer & Developer : Wang Rongtao LinLe GaoJie GanLu
Total 0.000000(s) query 1, Server time : 2024-03-29 04:21:03, Gzip enabled