UTS Open '15 #3 - Pogo

View as PDF

Submit solution


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

Author:
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 \leq N \leq 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 \leq M \leq 3), which means that if she is at tile x, she can travel to any tile y such that |x-y| \leq 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 \leq N \leq 10^5
10\%M=31 \leq N \leq 15
25\%M=21 \leq N \leq 10^5
30\%M=31 \leq N \leq 1000
30\%M=31 \leq N \leq 10^5

Input Format

A single line containing N and M.

Output Format

A single line containing the answer.

Sample Data

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

Comments

There are no comments at the moment.