ACM-ICPC-OJ训练营

问题 J: Journey with Knapsack

时间限制: 8 Sec 内存限制: 128 MB
提交: 4 解决: 1
[提交][状态][讨论版][命题人:]

题目描述

KazaQ has a knapsack with volume

2⋅n and

n kinds of food, where the

i-th food's volume is

i and the number of it is

(1≤i≤n) meaning that the number of the

i-th food that KazaQ would like to store into the knapsack is no more than

ai, otherwise he would feel sick. KazaQ has a unique taste, therefore all the

ai are distinct.

KazaQ plans to make a journey but after that he needs to store some food and one piece of equipment into the knapsack. He has

m pieces of equipment, of which the

i-th piece's volume is

(1≤i≤n). Notice that volumes of different pieces may be the same.

Assuming that two plans are distinct if and only if they contain different pieces of equipment or there exists at least one integer

(1≤k≤n) satisfying the number of the

k-th food to store into the knapsack in this two plans are different, KazaQ is intend to know what is the total number of distinct plans for storing one piece of equipment and some food into the knapsack fully. Can you help him?

The answer may be very large, so you only need to give the value of the answer modulo

109+7.

输入描述

The input contains multiple test cases.
For each test case:
The first line contains two positive integers

n and

m, satisfying

1≤n≤5⋅104,1≤m≤2⋅n.
The second line contains

n distinct non-negative integers

a1,a2,⋯,an, satisfying

0≤a1<a2<⋯<an≤2⋅n.
The third line contains

m positive integers

b1,b2,⋯,bm, satisfying

1≤b1,b2,⋯,bm≤2⋅n.
About

100 test cases in total, where no more than

5 cases satisfy

n≥103.

输出描述

For each test case, output "Case #x: y" in one line (without quotes), where

x indicates the case number starting from

1 and

y denotes the answer of corresponding case.

样例输入

样例输出

Case #1: 1
Case #2: 2
Case #3: 6