GAMECG - GAME

Ashton Carl McDonalds (known as A.C.M.) works at a small school. The school have decided to compete in a new style of game designed by programmers. This game is organized in teams, each team have the size of M competitors, the goal of the game is to each team solve the maximum number of problems, if there is a tie, the team who solved faster win. It is important to you know that the order of the members in a team doesn't matter.

Carl was designed by his school to be a kind of coach of this game. He needs to train all the teams of his school, and the most important, he needs to choose theses teams. A.C.M is kind of worried if it will be a lot of teams, and maybe it will be a lot of work to him. Due to this, he decides to count how many different teams can exist in his school.

McDonalds is not good on mathematics, due to this he asked you to count the number of different teams. A.C.M knows that the result can be very large, so he asked to you to give the result in modulus 1300031, but he needs to know if the result exceeds 1300030 or not.

Input

The input consists of several lines.

Each line consists of two integers N (1 <= N <= 10^6) and M (1 <= M <= N), the number of students and the numbers of members in each team.

Output

The output consists of two lines. The first line contains the result in modulus, and the second line contains “Exceeds” if the result exceeds 1300030 or “Does not exceed” if the result does not exceed 1300031.

Example

Input:
3 1
140 60
15 8

Output:
3
Does not exceed
207865
Exceeds
6435
Does not exceed

Added by:Mateus Dantas [ UFCG ]
Date:2012-02-26
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Phyllipe Cesar

hide comments
2015-04-11 13:30:30 Dhawal Harkawat
@Mateus Dantas [ UFCG ] , please check submission id : 14073629, giving WA. Help..
2012-02-26 16:53:21 Phyllipe Medeiros
You need to read until EOF and you can use scanf/printf.
2012-02-26 12:50:36 Mitch Schwartz
Reading until EOF, yes.

Input is quite large. I was only able to pass with fast I/O, although my approach is fine unoptimised for any other similar problem I've encountered on SPOJ. I guess the author had something special in mind.

Edit: Ok, I found a way to pass with scanf/printf.

Last edit: 2012-02-26 16:47:24
2012-02-26 08:53:08 mehmetin
We are reading until EOF, right?

Last edit: 2012-02-26 09:11:50
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.