{"raw_statement":[{"iden":"statement","content":"Hawawshi is a traditional dish in Egypt, it's really appreciated that there are people who are storing it in highly secure safes. The safes are encrypted by a pseudo-random number generator that generates a sequence of random numbers according to the equation: , where a, b, and p are integers, p is a prime number, and R0 is the first generated number which is also known as the seed of the sequence. \n\nSome secret information has been delivered to you that the seed of the random generator was an integer selected at random from the range [A, B] inclusively, furthermore, that the key number of the Hawawshi-safe is a number that appeared as one of the first N generated random numbers (namely, R0, R1, ..., RN - 1). You are going to try some different key numbers X, but first, you need to know what is the probability that X has appeared in the first N generated random numbers?\n\nThe first line of the input contains a single integer T specifying the number of test cases.\n\nEach test case consists of a single line containing seven integers N, X, A, B, a, b, and p.\n\n(1 ≤ N, X, A, B, a, b ≤ p - 1, 1 < p < 108, 1 ≤ A ≤ B ≤ min(100, p - 1)), in which p is a prime number.\n\nFor each test case, print a single line containing a reduced fraction q / r (q, r are integers) representing the probability that the number X appears in the first N generated random numbers (by the pseudo-random number generator given). It's guaranteed that it is possible to represent the probability as a reduced fraction of integers as requested.\n\nAs a demonstration of the pseudo-random number generator, if a = 2, b = 1, p = 7, R0 = 2, then the generated numbers are 2, 5, 4, 2, 5, 4, 2, 5, 4, ... .\n\nIn the last two test cases, a = 4, b = 7, p = 11, R0 = 5, and therefore the generated sequence is 5, 5, 5, ....\n\n"},{"iden":"input","content":"The first line of the input contains a single integer T specifying the number of test cases.Each test case consists of a single line containing seven integers N, X, A, B, a, b, and p.(1 ≤ N, X, A, B, a, b ≤ p - 1, 1 < p < 108, 1 ≤ A ≤ B ≤ min(100, p - 1)), in which p is a prime number."},{"iden":"output","content":"For each test case, print a single line containing a reduced fraction q / r (q, r are integers) representing the probability that the number X appears in the first N generated random numbers (by the pseudo-random number generator given). It's guaranteed that it is possible to represent the probability as a reduced fraction of integers as requested."},{"iden":"note","content":"As a demonstration of the pseudo-random number generator, if a = 2, b = 1, p = 7, R0 = 2, then the generated numbers are 2, 5, 4, 2, 5, 4, 2, 5, 4, ... .In the last two test cases, a = 4, b = 7, p = 11, R0 = 5, and therefore the generated sequence is 5, 5, 5, ...."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ G = (V, E) $ be a weighted undirected graph with $ |V| = N $, $ |E| = M $, and edge weights $ w: E \\to \\mathbb{Z}^+ $.  \nLet $ u \\in V $ be the starting node, $ L \\in \\mathbb{Z}^+ $ the path length (number of edges), and $ K \\in \\mathbb{Z}^+ $ with $ 1 \\leq K \\leq L $.  \n\n**Constraints**  \n1. $ 2 \\leq N \\leq 10^5 $, $ 1 \\leq M \\leq 10^5 $, $ 1 \\leq u \\leq N $, $ 1 \\leq L \\leq 10^5 $, $ 1 \\leq K \\leq L $  \n2. Edge weights satisfy $ 1 \\leq w(e) \\leq 10^9 $ for all $ e \\in E $  \n3. No self-loops or multiple edges  \n\n**Objective**  \nLet $ \\mathcal{P} $ be the set of all walks of exactly $ L $ edges starting at node $ u $ (edges and nodes may be revisited).  \nFor each walk $ p \\in \\mathcal{P} $, let $ W_p = (w_1, w_2, \\dots, w_L) $ be the multiset of edge weights along $ p $, sorted in non-decreasing order.  \nDefine $ f(p) = W_p[K] $, the $ K $-th smallest weight in $ p $.  \nCompute:  \n$$\n\\max_{p \\in \\mathcal{P}} f(p)\n$$","simple_statement":"You are given a weighted undirected graph. Start from node u, find all paths of exactly L edges (can reuse nodes/edges). For each path, sort the edge weights in ascending order and take the K-th smallest weight. Return the maximum of all these K-th weights.","has_page_source":false}