All Tracks Algorithms Dynamic Programming Introduction to Dynamic Programming 1 Problem

Help Patwari
/
No tags
Problem
Editorial
Analytics

Patwari is really good at killing his enemy. His tactics lies in the way he chooses his steps while chasing his enemy. And the tactic is that he chooses his steps such that (steps&1 == 1).
Now he wanted to know in how many ways he can kill his enemy K steps away from him. Order in which Patwari makes his steps does matters. Now as Patwari is not good in mathematics, he really wants your help to solve this problem! You have to print answer modulo 10^9 + 7

Input Format :

The only line of input contains an integer K (\(1≤K≤10^{5}\))

Output Format :

Output the Number of distinct ways mod \(10^{9}\) + 7

SAMPLE INPUT
5
SAMPLE OUTPUT
5
Explanation

the 5 ways are :

3 + 1 + 1

1 + 3 + 1

1 + 1 + 3

1 + 1 + 1 + 1 + 1

5

Time Limit: 0.2 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB

Best Submission

Similar Problems

Contributors

Initializing Code Editor...
Notifications
View All Notifications

?