SP18184 DURIN - Durins Day

Reference:: The Hobbit : Desolation of Smaug [The\_Hobbit:\_The\_Desolation\_of\_Smaug](http://en.wikipedia.org/wiki/The_Hobbit:_The_Desolation_of_Smaug) J. R. R. Tolkien decided to make Thorin Oakenshield’s task more difficult. This time he was given an infinite number of keys represented by a small string. The hidden entrance has a lot of keyholes side by side represented by one long string. The key fits only into a slit that matches it completely. Oakenshield does not know how many keys he would require and which all keyholes he will have to try out. So if there are **n** keyholes where the key fits, he might need any number of keys between **1 to n** (both inclusive). Moreover he does not know which keyholes among the ones where the keys fit, he will have to use. All he knows is that there is a unique way to open the door. Trying out each configuration takes **1** second. The last light of Durin’s day does not last long and will have to try out all possibilities before it goes. He wants you to find out how long, in the worst case, it will take for him to try out all possibilities. Since the answers may be huge, output it modulo **1000000007**. If there are no keyholes where the key fits, output 0.

N/A

N/A