TSSPC '20 Contest 1 P5 - Trick or Trail

View as PDF

Submit solution


Points: 17 (partial)
Time limit: 3.0s
Memory limit: 250M

Authors:
Problem type

It's Halloween and Henry_Zhang loves candy, but is too scared to go trick or treating (he's very afraid). He lives in a terrifying grid neighbourhood of dimension n x m. sankeeth_ganeswaran lives at (0,0) and he wants to deliver candy to Henry_Zhang who lives at (n,m). sankeeth_ganeswaran rides his old haunted broomstick but accidentally trips and squishes it, breaking it under all his weight! His broken broom can only fly him up or right on the grid. How many spooky paths can he take to get there? As the answer can be hauntingly large, find the answer modulo 10^9+7.

Input Specification

The first line contains two space-seperated integers 1 \leq n, m \leq 10^7

Output Specification

Output the amount of paths.

Subtasks

Subtask 1 [5%]

1 \leq n, m \leq 10

Subtask 2 [15%]

1 \leq n, m \leq 10^3

Subtask 3 [80%]

1 \leq n, m \leq 10^7

Sample Input 1

1 2

Sample Output 1

3

Explanation for Output 1

The following image depicts the 3 paths that he can take

Image

Sample Input 2

30 70

Sample Output 2

511931791

Explanation for Output 2

There are 29372339821610944823963760 paths, which is equivalent to 511931791 (\text{mod } 10^9 + 7)


Comments

There are no comments at the moment.