Sequence Sum
Little Kostya has many cards with numbers 1 to N on them. Last time he laid out the cards from 1 to N in increasing order and obtained a huge number. He could not figure out what to do with this number, but his dad, having noticed several strange properties of the number, proposed a task to a contest similar to the one you're now participating in.
Two years have passed. During this time many numbers have been laid out using the cards. However, Kostya does not like to lay out monotonous sequences any more. This is because his mom told him how many students were disappointed that they could not solve the first task about the cards.
As time progresses, the students keep asking for new tasks to solve. Now the dad, having mastered all his creative thoughts, decided that this time the students will have to solve the following: let's consider all integer sequences with lengths up to and elements in the range from 1 to N; now, let's exclude all the monotonous sequences (as you remember, there already was a task about them two years ago); next, let's view each of the sequences as a number written in base N+1; and finally - what could be easier - let's just sum them all. Of course, Kostya, still a little boy, probably would not be able to do this, but perhaps you can?
Р.S. The sequence a_1, a_2, ... , a_k is turned into the number .
Input
The only line of input consists of the integer N from 1 to 1000000000.
Output
The only line of output should consist of the sum described above. However, the actual value may be gargantuan, so you're asked to output it modulo 1000000007.
Note: For N=3 the possible sequences are 1, 2, 3, 11, 12, 13, 21, 22, 23, 31, 32, 33, 111, 112, 113, 121, 122, 123, 131, 132, 133, 211, 212, 213, 221, 222, 223, 231, 232, 233, 311, 312, 313, 321, 322, 323, 331, 332, 333, Of those, the following are non-monotono it's 11, 22, 33, 111, 112, 113, 121, 122, 131, 132, 133, 211, 212, 213, 221, 222, 223, 231, 232, 233, 311, 312, 313, 322, 323, 331, 332, 333.