You are given $$$2$$$ arrays $$$A$$$ and $$$G$$$ both of the same length $$$N$$$. You are asked to create a permutation $$$P$$$ of length $$$N$$$ such that for any pair of integers $$$i,j$$$ $$$(1 \le i,j \le n)$$$ where $$$i\neq j$$$ if $$$G_i = G_j$$$ and $$$A_i \ge A_j$$$ then it should satisfy that $$$P_i \gt P_j$$$.
Since there may be a lot of permutations that satisfy the above requirements, you are asked to print the lexicographically smallest permutation.
If there is no such permutation that satisfies the above requirements, print $$$ - 1 $$$.
The first line of input contains a single integer $$$T$$$, the number of test cases.
The first line of each test case contains a single integer $$$n$$$ $$$(1 \le n \le 10^5)$$$, the number of elements in each array.
The second line of each test case contains $$$n$$$ integers $$$A_1,A_2,\dots,A_n$$$ $$$(1 \le A_i \le 10^9)$$$, the elements of array $$$A$$$.
The third line of each test case contains $$$n$$$ integers $$$G_1,G_2,\dots,G_n$$$ $$$(1 \le G_i \le 10^5)$$$, the elements of array $$$G$$$.
The sum of $$$n$$$ over all test cases doesn't exceed $$$10^5$$$.
Print $$$T$$$ lines, each containing the lexicographically smallest permutation, or $$$-1$$$ if no such permutation exists.
2 8 1 8 1 7 4 6 6 5 1 2 2 2 1 2 1 1 8 1 8 1 4 4 7 6 5 1 8 2 2 1 7 4 1
1 5 2 4 6 3 8 7 1 2 3 4 5 6 7 8
For the second test case, we can check that the permutation satisfies the requirements.
Also, it's the lexicographically smallest permutation.
A permutation of length $$$N$$$ is a sequence of integers from $$$1$$$ to $$$N$$$ of length $$$N$$$ containing each number exactly once. For example, $$$[1], [4,3,5,1,2], [3,2,1]$$$ are permutations, and $$$[1,1], [0,1], [2,2,1,4]$$$ are not.
Sequence $$$X_1, X_2, \dots , X_N$$$ is lexicographically smaller than sequence $$$Y_1, Y_2, \dots , Y_N$$$ if there exists an integer $$$r$$$ $$$(0 \le r \lt N)$$$ such that $$$X_1 = Y_1, X_2 = Y_2, \dots , X_r = Y_r$$$ and $$$X_{r+1} \lt Y_{r+1}$$$.
You will be given an array $$$a$$$, a weighted tree, and some queries. To make things a lot simpler, the array $$$a$$$ will just be a permutation.
The queries are very simple:
"$$$1$$$ $$$l$$$ $$$r$$$": Reverse $$$a[l \dots r]$$$. $$$(r - l + 1 \le 30)$$$
"$$$2$$$ $$$v$$$ $$$k$$$": $$$v$$$ is a node in the tree. You will be given $$$k$$$ (not necessarily disjoint) ranges, the $$$i$$$-th $$$(1 \le i \le k)$$$ range is $$$[l_i, r_i]$$$. You have to calculate: $$$$$$OR_{i = 1}^{k}\sum_{j = l_i}^{r_i}dist(a_j, v)$$$$$$ Where $$$OR$$$ is bitwise OR and $$$dist(u, v)$$$ is the distance between $$$u$$$ and $$$v$$$ in the tree (i.e. the sum of weights of the edges on the simple path between $$$u$$$ and $$$v$$$).
In the first line of the input, you will be given an integer $$$t$$$ $$$(1 \le t \le 10^5)$$$ — the number of testcases.
The first line of each testcase will contain two integers $$$n$$$ and $$$q$$$ $$$(1 \le n, q \le 10^5)$$$ — the number of nodes in the tree, and the number of queries, respectively.
In the next line there will be $$$n$$$ integers $$$a_1, a_2, a_3, \dots, a_n$$$ $$$(1 \le a_i \le n)$$$. It is guaranteed that the array $$$a$$$ is a permutation.
The next $$$n - 1$$$ lines will contain the edges of the tree. Each line will contain three integers $$$u$$$, $$$v$$$ $$$(1 \le u, v \le n)$$$ and $$$w$$$ $$$(0 \le w \le 10^3)$$$, which represents the endpoints and the weight of the edge, respectively. It is guaranteed that the given edges form a tree.
The next $$$q$$$ lines will contain the description of the queries.
You will be given the queries in an encoded format. Let $$$prevAns$$$ be $$$0$$$ initially.
For queries of the type $$$1$$$, you will be given three integers on a single line. $$$type$$$, $$$l$$$, and $$$r$$$. Where $$$type$$$ will be equal to $$$1$$$ for queries of this type, and $$$(1 \le l \le r \le n,$$$ $$$r - l + 1 \le 30)$$$.
For queries of the type $$$2$$$, on the first line of the query, you will be given three integers $$$type$$$, $$$v'$$$, and $$$k$$$. Where $$$type$$$ will be equal to $$$2$$$ for queries of this type, and $$$(1 \le v' \le n,$$$ $$$1 \le k \le 10^5)$$$. Then, the real value of $$$v$$$ will be $$$$$$v = (((v' \oplus prevAns) \cdot v') \mod n) + 1$$$$$$ Then follows $$$k$$$ lines, each containing two integers $$$l'$$$ and $$$r'$$$ $$$(1 \le l' \le r' \le n)$$$. Then, the real values of $$$l$$$ and $$$r$$$ will be $$$$$$l = (((l' \oplus prevAns) \cdot l') \mod n) + 1$$$$$$ $$$$$$r = (((r' \oplus prevAns) \cdot r') \mod n) + 1$$$$$$ (where $$$\oplus$$$ is bitwise Exclusive OR).
If $$$r \lt l$$$, then swap them.
Then update the value of $$$prevAns$$$ to be equal to the answer to this query.
It is guaranteed that the sum of $$$n$$$ over all testcases will not exceed $$$10^5$$$, the sum of $$$q$$$ over all testcases will not exceed $$$10^5$$$, the sum of $$$k$$$ over all the queries of the type $$$2$$$ in the entire input file will not exceed $$$10^5$$$.
For each query of the type $$$2$$$, output a line containing a single integer, the answer to that query.
2 1 1 1 2 1 2 1 1 1 1 2 3 2 1 1 2 24 2 1 2 1 1 2 2 1 1 2 2 2 3 1 1 2 2 1 2
0 24 24
Explanation of the second testcase from the sample:
In the first query, $$$v$$$ is node $$$1$$$, and the ranges are $$$[1, 1]$$$ and $$$[2, 2]$$$, The answer is $$$24$$$ $$$OR$$$ $$$0$$$ $$$=$$$ $$$24$$$.
$$$prevAns$$$ is now $$$24$$$.
After the second query, the array becomes $$$[1, 2]$$$.
In the last query, $$$v$$$ is node $$$(((2 \oplus 24) \cdot 2) \mod 2) + 1 = 1$$$, and the ranges are $$$[2, 2]$$$, $$$[1,1]$$$, and $$$[1,2]$$$. The answer is $$$24$$$ $$$OR$$$ $$$0$$$ $$$OR$$$ $$$(0 + 24)$$$ $$$=$$$ $$$24$$$.
let's define some concepts:
Now, you are given an integer array $$$a$$$ and two integers $$$l,r\space (l\le r)$$$ and you are asked to distribute the elements of this array between two arrays $$$b$$$ and $$$c$$$ where each element $$$a_i$$$ must belong to exactly one of the arrays $$$b$$$ or $$$c$$$.
A distribution is called valid if the ugliness of $$$b$$$ is between $$$l$$$ and $$$r$$$.
Among all the valid distributions of $$$a$$$, you must find the one that minimizes $$$ |cost(b) - cost(c)| $$$.
Print the minimum value of $$$ |cost(b) - cost(c)| $$$ you can get or print $$$-1$$$ if there's no valid distribution.
The first line of the input contains a single integer $$$T$$$, ($$$1 \le T \le 20$$$), the number of test cases.
Each test case consists of two lines. The first line contains three space-separated integers $$$n, l, r$$$ ($$$1\le n\le 100$$$), ($$$1\le l\le r \le 55$$$).
The second line contains $$$n$$$ space separated integers $$$a_1,a_2,\dots,a_n$$$ ($$$1\le a_i\le 10^6$$$).
It is guaranteed that the sum of $$$n$$$ over all the test cases does not exceed $$$100$$$ and that the sum of $$$a_i$$$ over each test case does not exceed $$$10^6$$$.
For each test case, in a single line, if there's no valid distribution print $$$-1$$$ otherwise print the minimum possible value of $$$ |cost(b) - cost(c)|$$$.
3 6 2 4 1 1 2 2 2 2 6 1 6 1 1 1 1 1 1 6 1 6 2 2 2 2 2 2
0 -1 0
In the first test case, we distribute $$$a$$$ as follow: $$$b = 1,2,2$$$ , $$$c = 1,2,2$$$.
The ugliness of $$$b$$$ is $$$2$$$ which is satisfy $$$l\le 2\le r$$$.
The $$$cost(b) = 5, cost(c) =5$$$ so the answer is $$$|5-5|=0$$$ (the minimum possible answer).
We will create a new folder, and inside it, we will add a text file with the name $$$S$$$, then we will repeat the following $$$n$$$ times:
The files will be renamed as follows:
All copied files will have $$$-$$$C0000 added to the end of their names when being pasted.
For a file is being pasted, if there is another file that has the same name, instead of adding $$$-$$$C0000 we increase the counter of this suffix to be $$$-$$$C0001, and if there is still a file sharing the same name we keep increasing the counter until there is no file that has the same name.
See notes for more clarification.
You have to print the name of the file whose index is $$$k$$$ after sorting the renamed files, it is guaranteed that a solution exists for such $$$k$$$.
The first line of the input contains one integer $$$t$$$ $$$(1\le t\le 10^3)$$$ the number of test cases.
The first line of each test case contains a string $$$S$$$ $$$(|S|\le 10)$$$ the initial filename. The second line of each test case contains two integers $$$n$$$ $$$(1\le n\le 10^3)$$$, $$$k$$$ $$$(1\le k\le 10^{17})$$$ the number of times to copy all the files and the index of the file that you are asked its name.
It is guaranteed that $$$k$$$ is less or equal to the number of files created after making $$$n$$$ copies as demonstrated previously.
For each test case print a single string $$$F$$$ the filename at index $$$k$$$ after sorting all the filenames in lexicographical order.
2 Acm2022-23 2 1 Acm2022-23 2 2
Acm2022-23 Acm2022-23-C0000
After the first copying operation, we will have the following files.
After the second copying operation, we will have the following files.
after sorting the files lexicographically:
So, for the first test case, the answer will be the first file name after the second copying operation which is Acm2022-23.
In this contest, there is a superhero team with $$$n$$$ contestants, one of them is Naseem, while the contest is running he wants to go out to smoke, and while he is out he wonders how many members of his team are still in the contest.
The first line of input contains a single integer $$$T$$$ $$$(1 \le T \le 10^5)$$$, the number of test cases.
The next $$$T$$$ lines each contains a single integer $$$n$$$ $$$(1 \le n \le 10^5)$$$, the number of contestants in Naseem's team.
Print $$$T$$$ lines, each containing a single integer, the number of members of his team that are still in the contest.
237
2 6
Explanation of the first sample case:
Naseem's team consists of 3 people (including Naseem). After he went out, only 2 of them are now left in the contest.
Al-Aswad will give you a grid of size $$$n \times m$$$. Each cell $$$(i,j)$$$ has an integer value $$$a_{i,j}$$$.
We will consider two cells as adjacent if they have a common side.
Your task is to choose a non empty subset of adjacent cells in such a way that the sum of cells' value is as large as possible.
The first line of the input contains a single integer $$$T$$$, the number of test cases.
The first line of each test case contains two integers $$$n$$$ $$$(1 \le n \le 10^3)$$$ and $$$m$$$ $$$(1 \le m \le 9)$$$, the number of rows and the number of columns in the grid respectively.
The following $$$n$$$ lines contain $$$m$$$ integers each, the $$$j$$$-th element in the $$$i$$$-th line $$$a_{i,j}$$$ is the number written in the $$$j$$$-th cell of the $$$i$$$-th row $$$( |a_{i,j}| \le 10^5)$$$.
The sum of $$$n$$$ over all test cases doesn't exceed $$$10^3$$$.
For each test case print a single line containing one integer, the answer to the problem.
2 3 3 1 1 1 -1 -1 1 1 1 1 4 5 9 -6 -6 9 -2 6 4 -6 8 -9 8 -2 2 8 3 -6 4 6 2 5
7 72
For the first test case, You can select adjacent cells $$$(1,1), (1,2), (1,3), (2,3), (3,3), (3,2), (3,1)$$$. The sum of the values of these cells is $$$7$$$.
For the second test case, you can select all cells with positive values and the cell $$$(3,2)$$$, the sum will be: $$$27 - 2 + 47 = 72$$$. It can also be shown that this is the maximum possible sum.
Little Fermat has recently learned about digits sum. He became super strong that he could solve any problem regarding the sum of digits. Unfortunately, one day he became bored and he started to think about the sum of squares of digits instead of boring simple digits sum. He found that some numbers have amazing properties so he started to call them beautiful numbers! A beautiful number is a natural number that has these two conditions:
1. it doesn't have any zero ($$$0$$$) digit. ($$$174,3,8955$$$ don't have any zero digits while $$$1058,10,600$$$ have at least one zero digits).
2. the sum of the squares of its digits is a perfect square.
A perfect square is an integer that is the square of an integer; in other words, it is the product of some integer with itself.
As Little Fermat became obsessed with these numbers he wants to find a way to generate a beautiful number with $$$n$$$ digits.
Can you help Little Fermat?
The first line of the input contains one integer $$$T$$$ $$$(1 \le T \le 10^5)$$$, the number of test cases.
The next $$$T$$$ lines each contains a single integer $$$n$$$ ($$$1 \le n \le 10^{16}$$$), the number of digits the beautiful number should have.
You are Asked to find any beautiful number with n digits. if there is no such one print $$$ - 1 $$$.
Since the number could be extremely large and the order of digits doesn't matter, you are asked to print $$$9$$$ numbers, which represent the frequencies of the digits $$$1, 2, 3, 4, 5, 6, 7, 8, 9$$$ respectively.
2 1 4
0 0 0 0 0 0 0 0 1 0 4 0 0 0 0 0 0 0
In the first test case, $$$9$$$ is a beautiful number with one digit. In the second test case $$$2222$$$ is a beautiful number with four digits
The picture is to show the shape of the kite. Given an integer $$$n$$$, count the number of different kites in a regular $$$n$$$-gon.
A regular $$$n$$$-gon is a convex polygon consisting of $$$n$$$ equal-length sides and all its angles are equal.
A kite is a convex quadrilateral $$$A$$$ $$$B$$$ $$$C$$$ $$$D$$$, such that $$$AB = AD$$$ and $$$CB = CD$$$.
Two kites are considered different if they differ by at least one point.
The first line of the input contains a single integer $$$T \space (1 \le T \le 2 \cdot 10^5)$$$ - the number of test cases.
Then $$$T$$$ lines follow, each containing a single integer $$$n \space (4 \le n \le 10^9)$$$ - the number of sides of the polygon.
For each test case, print a single line containing the number of different kites in a regular $$$n$$$-gon.
2 4 5
1 0
Explanation of the sample:
In the first testcase, the only kite is the whole $$$4$$$-gon.
In the second testcase, there are no kites.
COVID-22 has spread in Aws's City. since humanity had suffered a lot from COVID-19, the army made a decision to destroy Aws's city.
Aws's City consists of $$$n$$$ buildings lined up in a row from left to right, the height of the $$$i$$$-th building is $$$h_i$$$.
The army has two types of bombs.
A neighborhood is a segment (consecutive sequence) of buildings $$$[l,r]$$$ $$$(l \lt r)$$$ where $$$(h_l, h_r \gt 0)$$$ and $$$h_r$$$ is the first building to the right of $$$h_l$$$ greater than or equal to $$$h_l$$$ (in other words, all buildings in the segment $$$[l+1,r-1]$$$ have heights less than $$$h_l$$$.
The army wants you to find the minimum cost to destroy all city buildings.
The first line of the input contains a single integer $$$T$$$, the number of test cases.
The first line of each test case contains three integers $$$n$$$, $$$x$$$, and $$$y$$$ $$$(1 \le n \le 500)$$$ $$$(1 \le x,y \le 10^9)$$$ the number of buildings in the city, the cost of destroying one building, and the cost of destroying a neighborhood respectively.
The second line of each test case contains $$$n$$$ integers describing the height of each building in Aws's city from left to right where $$$h_i$$$ $$$(1 \le h_i \le 10^9)$$$ is the height of building number $$$i$$$.
The sum of $$$n$$$ over all test cases doesn't exceed $$$500$$$.
For each test case, print a single integer representing the minimum possible cost to destroy all buildings in the Aws's city.
3 5 5 7 2 1 3 1 5 5 10 10 10 8 5 10 1 1 1 5 10
12 20 1
For the 1-st test case: First, destroy the building with index 3 using the first bomb with cost $$$x$$$. The city will become like this [2 1 0 1 5]. Then, destroy a neighborhood from index 1 to index 5 with a cost of $$$y$$$. The total cost to destroy all the buildings = 1*$$$x$$$ + 1*$$$y$$$.
For the 2-nd test case: First, destroy a neighborhood from index 1 to index 4 with cost y. The city will become like this [0 0 0 0 1] Then, destroy the last building using the first bomb with cost x. The total cost to destroy all the buildings = 1*$$$x$$$ + 1*$$$y$$$.
For the 3-rd test case: The only way to destroy the only building in the city is by using the first bomb with cost $$$x$$$.
A permutation is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[1, 2, 4, 3]$$$ is a permutation, but $$$[1, 3, 3, 2]$$$ is not a permutation because $$$3$$$ appears twice in the array, and $$$[1, 2, 4, 5]$$$ is also not a permutation because $$$n = 4$$$ but there is $$$5$$$ in the array.
Your task is to construct a permutation of length $$$n$$$, such that every pair of adjacent numbers in the permutation has an even product.
More formally, for each $$$i$$$ $$$(1 \le i \lt n)$$$, the following condition must hold:
The first line of input contains a single integer $$$T$$$, the number of test cases.
The next $$$T$$$ lines each contains a single integer $$$(1 \le n \le 10^{5})$$$, the size of the permutation.
The sum of $$$n$$$ over all testcases doesn't exceed $$$10^5$$$.
Print $$$T$$$ lines, each containing a permutation of $$$n$$$ space-separated integers such that every pair of adjacent numbers in the permutation has an even product. if there are multiple answers print any of them.
2612
2 1 6 5 4 3 2 9 8 7 4 5 6 1 12 3 10 11
AbdulQader is a tech genius. he spent many years mastering the Art of Networking, so when he knew the SCPC needs volunteers for IT support, he signed in right away.
During the contest, a sudden error caused the server to crash. having no time to set up a new server, AbdulQader decides to connect every two computers $$$directly$$$.
The contest has $$$n$$$ computers and a central switch of $$$\frac{n(n-1)}{2}$$$ connection points lined up in a row (numbered from $$$1$$$ to $$$\frac{n(n-1)}{2}$$$). To connect any two computers $$$directly$$$ you have to connect them to the same connection point. Each connection point can be connected to at most two computers.
The latency $$$X_i$$$ of a computer $$$i$$$ equals $$$X_i = p_e - p_s$$$ where :
AbdulQader knows that as $$$latency$$$ gets bigger the connection gets slower, so he wants to connect computers in a way to make the sum of total $$$latency$$$ for all the computers $$${\sum_{i = 1}^n X_i}$$$ as minimum as possible. Can you help him find that order?
Note that you have to connect each two exactly once.
The first line of the input contains a single integer $$$T$$$, the number of test cases.
The next $$$T$$$ lines each contains a single integer $$$n$$$ ($$$2 \le n \le 500$$$), the number of computers.
The sum of $$$n$$$ over all test cases doesn't exceed $$$500$$$.
For each test case print $$$m=\frac{n(n-1)}{2}$$$ lines where the $$$i^{th}$$$ line contain two integers $$$a,b$$$ $$$(1 \le a,b \le n)$$$ which represents a connection between computers $$$a$$$ and $$$b$$$ at the connection point $$$i$$$.
1 3
2 1 3 2 1 3
We can connect: computers 1 and 2 at connection point 1, computers 2 and 3 at connection point 2, computers 1 and 3 at connection point 3, so that total $$$latency$$$ = 2 + 1 + 1 = 4
Construct an $$$n \times n$$$ grid with numbers from $$$1$$$ to $$$n \times n$$$ (each number exists exactly once) such that there is no row nor column that contains a subsequence (has exactly more than $$$2$$$ elements) which forms an Arithmetic Progression.
Arithmetic Progression is a sequence of numbers in order, in which the difference between any two consecutive numbers is a constant value.
The first line of input contains a single integer $$$T$$$, the number of test cases.
The next $$$T$$$ lines each contains a single integer $$$n$$$ $$$(3 \le n \le 500)$$$, the dimension of the grid.
The sum of $$$n$$$ over all test cases doesn't exceed $$$500$$$
For each test case with input $$$n$$$ print n lines each having n integers describing the required grid. It is guaranteed that there is always one solution at least. If there are multiple answers print any of them.
1 3
1 3 2 7 9 8 4 6 5
Ali and Nour have decided to play a mobile game, the game will give an integer $$$x$$$ to Ali and an integer $$$y$$$ to Nour.
Each second, the game will print a number. It will print the numbers $$$1,$$$ $$$2,$$$ $$$3,$$$ $$$\dots$$$ in that order.
For each number, either Ali can take that number and subtract it from $$$x$$$ or Nour can take that number and subtract it from $$$y$$$.
The game ends when $$$x \le 0$$$ and $$$y \le 0$$$.
Since the battery of their device is running low, they want to finish the game as quickly as possible. Your task is to find the minimum number of seconds needed to finish the game.
The first line of input contains a single integer $$$T$$$ $$$(1 \le T \le 10^5)$$$, the number of test cases.
The next $$$T$$$ lines each contain two space-separated integers $$$x$$$ and $$$y$$$ $$$(1 \le x, y \le 10^{18})$$$ - the numbers given to Ali and Nour by the game.
Print $$$T$$$ lines, each containing a single integer, the minimum number of seconds needed to finish the game by making $$$x \le 0$$$ and $$$y \le 0$$$.
2 4 7 6 4
5 4
Explanation of the sample:
In the first test case, Ali will take $$$1$$$, $$$2$$$, and $$$3$$$, then Nour will take $$$4$$$ and $$$5$$$, so they can finish the game in 5 seconds.
In the second test case, Nour will first take $$$1$$$, then Ali will take $$$2$$$, then Nour will take $$$3$$$, and finally, Ali will take $$$4$$$, so they can finish the game in 4 seconds.
We got some leaks from the most dangerous place ever [Not Safe] that Baraa hates long statements.
So we decided not to write a story for this problem :D.
Given $$$N\times M$$$ points on a two dimensional-grid with coordinates $$$(x_i,y_j)=(a\times i,b\times j)$$$ where a,b are given integer values and for all possible pairs $$$i,j(1\le i\le N,1\le j\le M)$$$.
Each second exactly one action will happen, either all points will move down simultaneously or they will move left simultaneously, and the action will happen randomly with a probability of $$$\frac{1}{2}$$$.
Points on-axis OX can't move down anymore even if the action was moving all points down, the same goes for points on axis OY that they can't move left if the action was moving all points left.
In other words, if the action is move down, all points with coordinates $$$(x,y)$$$ where $$$(y \gt 0)$$$ will move to the position $$$(x,y-1)$$$. And if the action is move left, all points with coordinates $$$(x,y)$$$ where $$$(x \gt 0)$$$ will move to the position $$$(x-1,y)$$$.
Note that More than one point can have the same coordinates at the same time.
When a point has a coordinate $$$(0,0)$$$ it will disappear instantly.
$$$K$$$ actions happened, and you are now asked the expected number of points that still exist on the grid.
The first line contains one integer $$$T$$$, the number of test cases.
Each of the following $$$T$$$ lines contains $$$5$$$ integers $$$N, M,a,b,K$$$ $$$(1\le N,M,a,b\le 10^9,0\le K\le 2\times 10^5)$$$ Where $$$N,M$$$ determine the number of points in the grid, $$$a,b$$$ determine the coordinates of the points and $$$K$$$ represents the number of moves.
The sum of $$$K$$$ over all test cases doesn't exceed $$$2\cdot 10^5$$$.
Print the expected number of points that still exist on the grid modulo $$$10^9+7$$$.
Formally, let $$$MOD=10^9+7$$$. It can be demonstrated that the answer can be presented as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q\not\equiv0(\mod MOD)$$$.
Output a single integer equal to $$$(p\times q^{-1})\mod MOD$$$. In other words, output an integer $$$x$$$ such that $$$0\le x \lt M$$$ and $$$x\times q\equiv p(\mod MOD)$$$.
3 1 1 1 1 1 1 1 1 1 2 5 4 2 3 7
1 500000004 140625020