UTS Open '15 #3 - Pogo

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 0.6s
Memory limit: 64M

Problem types

Ms. Evans has decided to spice up her daily commute by traveling to work on a pogo stick. The sidewalk on her path to work is composed of N concrete tiles (1 \le N \le 10^5) numbered from 1 to N. Ms. Evans starts at tile 1 and wants to end at tile N. Her pogo stick has power M (1 \le M \le 3), which means that if she is at tile x, she can travel to any tile y such that |x-y| \le M.

Ms. Evans doesn't want to visit any tile more than once, since that would be boring. However, she enjoys jumping so much that she wants to make the maximum number of jumps possible. Please calculate the number of ways she can travel to work while fulfilling the above constraints. Since this number may be very large, you should output it modulo 10^9+7.

Portion of marksConstraints on MConstraints on N
5\%M=11 \le N \le 10^5
10\%M=31 \le N \le 15
25\%M=21 \le N \le 10^5
30\%M=31 \le N \le 1000
30\%M=31 \le N \le 10^5

Input Specification

A single line containing N and M.

Output Specification

A single line containing the answer.

Sample Data

1 11
3 21
8 29
5 36
11 3541
2015 2166449575