Processing math: 100%

Problem #102

Chinese Whispers

Consider a group of 5011 friends and a particular person in the group (say L). L has a message to spread around. Define a “whisper” as an instance where a friend passes the message to another friend. Considering all friends to be distinct, L is interested in finding out the number of sequences of 999983 “whispers” after which he will eventually get the message back. Calculate the answer modulo 1000000007.

Note:

  1. After a whisper, if A passed the message to B, then only B can whisper to others since only he has the message. Others can’t.

  2. During the sequence of whispers, there can be a point in time where A would get the message after less than 999983 whispers. In that case, he again should pass the message to others in order to complete a total of 999983 whispers

dp

Contributed by M Sai Varun Reddy

Solved by 37 users

Log in to submit answers.

Is something wrong?

Maintaining a collection of high quality questions is our top priority. If, however, you do find an error, report the problem and we'll make sure it is reviewed soon.