ZUFEOJ Home ProblemSet Source/Category Contest Status Ranklist F.A.Qs
Login Register

4667: The Wall (medium)

内存限制：256 MB 时间限制：2 S 标准输入输出
题目类型：传统 评测方式：文本比较 上传者：
提交：2 通过：2
提交提交记录统计Web Board

题目描述

D2。The Wall(中号)

每次测试的时间限制

2秒

每次测试的内存限制

256字节

输入

标准输入

输出

标准输出

奶牛海蒂惊呆了:北墙有裂缝了?僵尸聚集在外面，成群结队，准备攻击?这绝不能发生!她迅速拿出她的HC2(疯狂结构手册)，寻找正确的章节:

如何筑墙:

拿一组砖。

选择一个可能的墙壁设计。计算可能的设计的数量留给读者作为练习。

根据所选择的设计，将砖一块一块地放在上面。

这似乎很简单。但海蒂是一头编码牛，不是一只构建牛。她的思想总是回到2b点。尽管僵尸袭击的危险迫在眉睫，她想知道她可以用n块砖建造多少堵墙。

墙是简单版本中定义的一组墙段。有多少种不同的墙可以建造，使墙由至少1个，最多n个砖?两堵墙是不同的，如果有一列c和一列r，使得一堵墙在这个位置上有砖块，而另一堵墙没有。

除了n，你将得到C，墙的宽度(在简单版本中定义)。返回对106+3取模的不同墙壁的数量。

输入

第一行包含两个用空格分隔的整数n和C, 1≤n≤500000,1≤C≤200000。

输出

打印出海蒂可以建造的不同墙壁的数量，对106+3取模。

例子




Heidi the Cow is aghast: cracks in the northern Wall? Zombies gathering outside, forming groups, preparing their assault? This must not happen! Quickly, she fetches her HC2 (Handbook of Crazy Constructions) and looks for the right chapter:
How to build a wall:
  1. Take a set of bricks.
  2. Select one of the possible wall designs. Computing the number of possible designs is left as an exercise to the reader.
  3. Place bricks on top of each other, according to the chosen design.
This seems easy enough. But Heidi is a Coding Cow, not a Constructing Cow. Her mind keeps coming back to point 2b. Despite the imminent danger of a zombie onslaught, she wonders just how many possible walls she could build with up to n bricks.
A wall is a set of wall segments as defined in the easy version. How many different walls can be constructed such that the wall consists of at least 1 and at most n bricks? Two walls are different if there exist a column c and a row r such that one wall has a brick in this spot, and the other does not.
Along with n, you will be given C, the width of the wall (as defined in the easy version). Return the number of different walls modulo 106+3.
Input
The first line contains two space-separated integers n and C, 1≤n≤500000, 1≤C≤200000.
Output
Print the number of different walls that Heidi could build, modulo 106+3.
Examples
Input 
5 1
Output 
5
Input 
2 2
Output 
5
Input 
3 2
Output 
9
Input 
11 5
Output 
4367
Input 
37 63
Output 
230574
Note
The number 106+3 is prime.
In the second sample case, the five walls are: 
 B        B
B., .B, BB, B., and .B
In the third sample case, the nine walls are the five as in the second sample case and in addition the following four: 
B    B
B    B  B        B
B., .B, BB, and BB

输入样例 复制

输出样例 复制

分类标签