DreamGrid is a famous coach of competitive programming. He is so kind that many competitors are willing to ask him for advice. DreamGrid meets exactlyn competitors every day in his office, an
DreamGrid is a famous coach of competitive programming. He is so kind that many competitors are willing to ask him for advice. DreamGrid meets exactly n competitors every day in his office, and thus n "arriving" events and n "selecting" events will happen. An arriving event at time t indicates that a competitor arrives at the waiting room of the office at time t , and a selecting event at time t indicates that DreamGrid randomly selects (with equal probability) a competitor from the waiting room to talk with. Of course, if the selecting event happens, the waiting room must not be empty. After the talk, the competitor leaves the office and never comes back. After several days, DreamGrid starts to be curious about the average of the total expected waiting time of every competitor in all valid cases. The waiting time of a competitor is the time he is selected by DreamGrid minus the time he arrives at the waiting room. A case is a sequence of length 2n consisting of n arriving events and n selecting events, where the i -th event will happen at time ai . For a valid case, it must be satisfied that when a selecting event happens, the waiting room must not be empty. For example, let's denote an arriving event as 'A', and a selecting event as 'S'. If n = 2,a1 = 1,a2 = 2,a3 = 3, and a4 = 4, then the sequence "AASS" is valid, but the sequence "ASSA" is not valid, as the "selecting" event happening at time a3 = 3 is not valid. As the answer may not be an integer, you are supposed to calculate ab-1 mod p , where ( a and b are coprime) is the answer, p > 2n and is p prime, and is the modular multiplicative inverse b of with respect to the modulus p. It's easy to prove that the prime factors of b will never be larger than 2n.
