UTS Open '15 #3 - Pogo - Olympiads Online Judge

UTS Open '15 #3 - Pogo

Points: 25 (partial)

Time limit: 0.6s

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$ ~N~ concrete tiles $(1 \le N \le 10^5)$ ~(1 \le N \le 10^5)~ numbered from $1$ ~1~ to $N$ ~N~. Ms. Evans starts at tile $1$ ~1~ and wants to end at tile $N$ ~N~. Her pogo stick has power $M$ ~M~ $(1 \le M \le 3)$ ~(1 \le M \le 3)~, which means that if she is at tile $x$ ~x~, she can travel to any tile $y$ ~y~ such that $|x-y| \le M$ ~|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$ ~10^9+7~.

Portion of marks	Constraints on $M$ ~M~	Constraints on $N$ ~N~
$5\%$ ~5\%~	$M=1$ ~M=1~	$1 \le N \le 10^5$ ~1 \le N \le 10^5~
$10\%$ ~10\%~	$M=3$ ~M=3~	$1 \le N \le 15$ ~1 \le N \le 15~
$25\%$ ~25\%~	$M=2$ ~M=2~	$1 \le N \le 10^5$ ~1 \le N \le 10^5~
$30\%$ ~30\%~	$M=3$ ~M=3~	$1 \le N \le 1000$ ~1 \le N \le 1000~
$30\%$ ~30\%~	$M=3$ ~M=3~	$1 \le N \le 10^5$ ~1 \le N \le 10^5~

Input Specification

A single line containing $N$ ~N~ and $M$ ~M~.

Output Specification

A single line containing the answer.

Sample Data

Input	Output
1 1	1
3 2	1
8 2	9
5 3	6
11 3	541
2015 2	166449575

Comments

-5

can definitely solve contest problems in 4 seconds commented on Oct. 21, 2023, 11:02 p.m.

LESSGOOO 25 POINTER IN LUAAAAAAAA

This comment is hidden due to too much negative feedback. Show it anyway.