Once upon a time, there was a king named “Hirak Raj”. He was so cruel and greedy that farmers in his kingdom had to pay taxes even when they were starving. Diamonds were accumulated in his treasury, but the workers in the mine were not paid properly. Those who tried to protest were taken to “Jantar-mantar Ghar”, the chamber for brainwashing people. The king divided his kingdom into R regions. People in one region could communicate by sending letters to any other person within the same region but no letter could be sent from one region to another. A reputed teacher named “Udayan Pandit” was preparing to revolt against the king by educating his disciples in all the regions of the kingdom. Most of his disciples wrote encrypted letters to each other to fix the time and place of their meetings. Any disciple would always forward any letter (s/he wrote or received from others) to other disciples s/he knew in the same region. Udayan Pandit called a collection of his disciples a “group” if a letter written by any member of that group would eventually reach all other members of the group. Moreover, a group always contained the maximal number of disciples, i.e. no more disciple could be added to a group without violating the property stated above. Hirak Raj knew all the information about who was communicating with whom, but his police could not decipher the encrypted letters and distinguish the secret letters from other normal letters. Soon Hirak Raj became very desperate to find all the miscreants in the kingdom who want to dethrone him. He ordered every citizen to be taken to an updated version of “Jantar-mantar Ghar”, where a device was installed to determine whether a citizen had any intention to revolt or not. All the citizens classified as miscreants were arrested immediately. But the king was not satisfied with the efficiency of the machine. So he made another rule: any citizen who was not yet taken to jail would be arrested if at least K members of his/her group were already classified as miscreants by the device. Udayan Pandit noticed that the device in “Jantar-mantar Ghar” is faulty. It classified any person as a miscreant with probability p without depending on any information of that person. So, he wanted to know the expected number of arrested disciples in every region of the kingdom. Input The first line of input file contains a single integer, T (1 ≤ T ≤ 10). Then T test cases follow. Each case starts with a line containing two integers, R (1 ≤ R ≤ 20) and K (1 ≤ K ≤ 2000) and two more integers a and b (0 < a < b ≤ 1000), where a/b = p, the probability of classifying a disciple as a miscreant. Then there will be descriptions of the communications in those R regions. Each description starts with a line containing two integers, n (2 ≤ n ≤ 50000), number of Udayan Pandit’s disciples in the region and m (1 ≤ m ≤ 100000), the number of communications between two disciples. Then m lines follow. Each of these m lines contains two integers u and v (1 ≤ u, v ≤ n and u ̸= v), indicating disciple u forwards any letter (s/he wrote or received from others) to disciple v. Output For each case, output ‘Case x:’ in a separate line, where x denotes the case number. Then there will be R lines of output for each case. For each of these R lines, output ‘Region y: z’, where y is the region number (starting from 1 to R) and z is the expected number of disciples arrested. Suppose, z = u/v in the reduced form. Print u ∗ (v−1) mod 1000000007(109 + 7), where v−1 is the inverse of v mod 1000000007. You may assume that there will be unique modular inverse v−1 mod 1000000007.
2/2 Explanation of Region 1 in the 1st test case: There are only two disciples in the region and they form a group. Let x be the random variable which denotes the number of disciples arrested. So, E[x] = 1 ∗ Pr(x = 1) + 2 ∗ Pr(x = 2). Now, Pr(x = 1) = Pr(1 was classified as miscreant by the device and 2 was not) + Pr(2 was classified as miscreant by the device and 1 was not) = 0.5 ∗ 0.5 + 0.5 ∗ 0.5 = 0.5. For the remaining part, P r(x = 2) = P r(Both 1 and 2 were classified as miscreants by the device) + Pr(Either 1 or 2 was classified as miscreant by the device and the other one was arrested later) = 0.5 ∗ 0.5 + 0 = 0.25. So, E[x] = 1 ∗ 0.5 + 2 ∗ 0.25 = 1, which is the expected number of arrested disciples. Sample Input 2 2212 22 21 12 45 12 23 13 34 42 2112 45 12 23 13 21 34 22 21 12 Sample Output Case 1: Region 1: 1 Region 2: 375000005 Case 2: Region 1: 500000006 Region 2: 500000005