Temple Run
Problem
On a fine day , surya visits a temple kamakhiya . After worshipping goddess kali , he saw N donation boxes infront of him in a line . He has N identical coins each of one rupee . He don't want to donate more than K coins after visiting K boxes . Surya wonders in how many ways he can donate his N coins.
You have to report the number of ways he could do so mod 109+7 .
Input :
First line contains N .
Output :
Output Number of different ways mod 109+7 .
Constraints
0≤N≤105
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation
3 Donation boxes are differentiated by 2 bars " | " and numbers in between them represents number of 1 rupees coins in them . Different possible configurations are :
a) 1 | 1 | 1
b) 0 | 2 | 1
c) 0 | 0 | 3
d) 0 | 1 | 2
e) 1 | 0 | 2
