Problem A

Animal Farm
Time limit: 2 seconds
Memory limit: 2048 megabytes

Problem Description
On Animal Farm, the animals have rebelled against their human owner and have taken over
the management of the farm. To ensure equality and fairness among all the animals, they have
decided to create a new set of rules. However, as the new leaders, the pigs have started making
changes to the rules to favor themselves.

The farm maintains a hierarchy of animals based on their species, with each animal assigned
a specific influence level. This influence level, represented as a positive integer, determines the
animal’s priority in decision-making. Within a group, an animal can make decisions if it has
the highest influence level among the members.

The pigs have a plan to maximize their collective influence in the leadership council by selecting
a specific group of animals. Given a list of animals with their species and influence levels, you
are tasked to form the most influential leadership council while adhering to the following rules:

1. Only one pig species is allowed in the council to avoid power conflicts among the pigs.

2. Every council member of non-pig species should have an influence level less than the
influence level of the only pig’s in the council.

Determine the maximum total influence levels of the council that can be formed under these
rules.

Input Format
The first line contains an integer n, representing the number of animals. The next n lines each
contain a string species and a positive integer influence:

• species is a string representing the species of the animal, e.g., “pig”, “horse”, “cow”,
etc.
• influence is an integer representing the influence level of the animal.

Output Format
Output a single integer, the maximum total influence levels of the leadership council that can
be formed following the rules.

Technical Specification
• 1 ≤ n ≤ 105 .

1
 • The length of species is at most 10.
• species consists of only English characters in lowercase.
• At least one animal’s species is pig.
• influence is at most 108 .

Sample Input 1 Sample Output 1

5 10
pig 10
horse 15
pig 5
cow 20
sheep 25

Sample Input 2 Sample Output 2

5 25
pig 10
horse 15
pig 15
cow 15
sheep 10

2
 Problem B
Business Magic
Time limit: 2 seconds
Memory limit: 2048 megabytes

Problem Description
There are n stores located along a street, numbered from 1 to n from nearest to farthest. Last
month, the store k had a net profit of rk . If rk is positive, it represents a profit of rk dollars; if
rk is negative, it represents a loss of −rk dollars.

As a master of business magic, you have two types of spells at your disposal that you can use
to alter the net profits of these stores for the next month:

1. Blue Magic: You can choose a single continuous interval [L, R]. The effect of this spell
will be to double the net profit of every store from store L to store R (inclusive) for the
next month. That is, if k ∈ [L, R], then store k will have net profit 2rk next month.

2. Green Magic: You can choose any store and cast the green magic on it. The effect of
the green magic is to change the next month’s net profit of that store to the negative of
its last month’s net profit.

Any store that has not been affected by either spell will have the same net profit next month
as it did last month.

However, there are some restrictions when casting spells. You can only cast the blue magic
once and it must be used before the green magic. Additionally, the green magic cannot be cast
on any store that has already been affected by the blue magic. Your task is to determine the
maximum possible sum of the net profits for all stores for the next month after casting your
spells optimally.

Input Format
The first line contains an integer n, the number of stores. The second line contains n space-
separated integers r1 , r2 , . . . , rn , where rk is the net profit of store k last month.

Output Format
Output a single integer, the maximum possible total net profit of all stores for the next month
after casting the spells optimally.

Technical Specification
• 1 ≤ n ≤ 3 × 105
• −109 ≤ rk ≤ 109 for k ∈ {1, 2, . . . , n}

3
Sample Input 1 Sample Output 1
5 20
-2 5 -3 4 -1

Sample Input 2 Sample Output 2

7 7
-1 -1 -1 -1 -1 -1 -1

Sample Input 3 Sample Output 3

4 5724883756
998244353 864197532 -7 1000000000

4
 Problem C
Cards
Time limit: 2 seconds
Memory limit: 2048 megabytes

Problem Description
Diana is a student who likes to play various types of board games. Today, she receives a deck
of cards from her teacher as her birthday gift!

The deck of cards is special: there are n cards in the deck, and each card has a number on
its front and another number on its back. Each number on the front or the back is an integer
from 1 to n. Furthermore, all n numbers on the front are unique, and so are the n numbers on
the back. In other words, numbers on the front and the back are two different permutations of
numbers from 1 to n.

Apart from board games, Diana is also interested in mathematics and computer science. While
she is playing with those cards, the concept of inversions in a permutation comes to her mind.
An inversion is defined as a pair of indices (i, j) such that i < j and the element at position i
is greater than the element at position j. In other words, an inversion represents a situation
where two elements are “out of order” relative to their positions. A permutation has inversion
count c if there are c inversions can be found within it.

Diana wonders if she could rearrange the cards in some order so that the permutation on the
front has the same inversion count as the permutation on the back (she cannot flip or throw
away some cards). She cannot solve the problem in a while, so she wants to hear your solution.

In formal, you are given two permutations of integers from 1 to n: a1 , a2 , . . . , an and b1 , b2 , . . . , bn .

You have to find another permutation of the first n positive integers p1 , p2 , . . . , pn , such that
a′ = [ap1 , ap2 , . . . , apn ] and b′ = [bp1 , bp2 , . . . , bpn ] have the same inversion count. Output the
sequences a′ and b′ .

Input Format
The first line of the input contains an integer n, denoting the number cards in the deck. The
second line of the input contains n integers a1 , a2 , . . . , an , where ai is the number on the front
of the i-th card. The third line of the input contains n integers b1 , b2 , . . . , bn , where bi is the
number on the back of the i-th card.

Output Format
If it is impossible to rearrange the cards so that the aforementioned condition is satisfied,
print No. Otherwise, print Yes in the first line of the output. Then in the second line of the

5
output, print n integers a′1 , a′2 , . . . , a′n , denoting the numbers on the front of the cards after
the rearrangement. In the third line of the output, print n integers b′1 , b′2 , · · · , b′n , denoting the
numbers on the back of the cards after the rearrangement.

If there are multiple possible solutions, print any of them.

Technical Specification
• 1 ≤ n ≤ 5 × 105
• 1 ≤ ai ≤ n for i ∈ {1, 2, . . . , n}
• 1 ≤ bi ≤ n for i ∈ {1, 2, . . . , n}
• It is guaranteed that a1 , a2 , . . . , an and b1 , b2 , . . . , bn are both permutations of integers
1, 2, . . . , n.

Sample Input 1 Sample Output 1

5 Yes
2 5 1 4 3 3 1 5 2 4
4 2 5 3 1 1 5 2 4 3

Sample Input 2 Sample Output 2

4 No
2 4 1 3
3 1 2 4

Sample Input 3 Sample Output 3

10 Yes
7 4 3 1 6 10 5 2 9 8 2 3 8 1 4 5 9 6 7 10
8 6 2 9 5 10 7 1 4 3 1 2 3 9 6 7 4 5 8 10

Sample Input 4 Sample Output 4

7 Yes
1 2 3 4 5 6 7 1 2 3 4 5 6 7
1 2 3 4 5 6 7 1 2 3 4 5 6 7

6
 Problem D
Disbursement on Quarantine Policy
Time limit: 2 seconds
Memory limit: 2048 megabytes

Problem Description
The 2019 novel coronavirus, COVID-19, can be transmitted between humans through
water droplets and close contact. The transmission is especially easy and fast in
relatively crowded or confined spaces, such as airplanes or trains. If someone is infected
with COVID-19, then passengers occupying the adjacent seats will be infected easily.

—“Quarantine Policy,” 2023 ICPC Taoyuan Regional Contest, Problem D

There is a train with n rows, and there are m seats per row. All seats are occupied. For
some passengers, we know they are being infected with COVID-19 or not. However, for other
passengers, we are not sure about their status, and we assume each of them has 12 chance being
infected with COVID-19, independent from each other.

All infected passengers need to be quarantined for d0 days. All passengers that are not infected,
but edge-adjacent to any infected passenger, need to be quarantined for d1 days. All passengers
that are not infected, not edge-adjacent to any infected passenger, but corner-adjacent to any
infected passenger, need to be quarantined for d2 days.

The passengers need to stay in the hotel during quarantine. According to the regulations, the
government needs to pay for the hotel. As an accountant of the government, you are asked
to evaluate the expected total number of days the passengers need to be quarantined, which
indicates the expected total cost on paying for the hotel.

For example, suppose n = 4, m = 4, d0 = 15, d1 = 7, d2 = 3. The third passenger in the third

row is infected, and we don’t know whether the second passenger in the first row is infected or
not. Other 14 passengers are not infected.

If the second passenger in the first row is infected, then the total number of days of quarantine
is 91:

7 15 7 0
3 7 7 3
0 7 15 7
0 3 7 3

If that passenger is not infected, then the total number of days of quarantine is 55:

7
0 0 0 0
0 3 7 3
0 7 15 7
0 3 7 3

So the expected total number of days of quarantine is 91+55

2
= 73.

Input Format
The first line contains five integers n, m, d0 , d1 and d2 . The following n lines contain m
characters each. The j-th character of the i-th line represents the passenger occupying the j-th
seat of the i-th row. Each character is one of ‘V’, ‘.’, or ‘?’. ‘V’ means an infected passenger, ‘.’
means a not infected passenger, and ‘?’ means a passenger that has 12 chance being infected.

Output Format
The expected total number of days the passengers need to be quarantined, modulo 109 + 7.
It can be proved that the answer can be represented by a rational number pq where q is not
a multiple of 109 + 7. Then you need to print p × q −1 modulo 109 + 7, where q −1 means the
multiplicative inverse of q modulo 109 + 7.

Note: If x × q ≡ 1 mod 109 + 7, then x is the multiplicative inverse of q modulo 109 + 7.

Technical Specification
• 1 ≤ n ≤ 100
• 1 ≤ m ≤ 100
• 0 ≤ d2 ≤ d1 ≤ d0 ≤ 100

Sample Input 1 Sample Output 1

4 4 15 7 3 73
.?..
....
..V.
....

Sample Input 2 Sample Output 2

2 2 1 1 1 750000009
??
??

8
 Problem E
Efficient Slabstones Rearrangement
Time limit: 2 seconds
Memory limit: 2048 megabytes

Problem Description
Barbara has a garden. The garden is long and narrow, divided into m equal-sized regions
arranged in a row. Her friend, Babara, gave her n slabstones as birthday present. Barbara
then placed these slabstones in her garden, so she can enjoy stepping slabstones from one to
another every day. The i-th slabstone fully occupies the li -th to ri -th region of the garden. The
slabstones do not overlap, and any two slabstones have at least d empty regions between them.

Below is a valid placement of the slabstones with m = 15, n = 3, d = 2, and the three slabstones
occupy the regions 2–4, 7–7, 12–13 respectively.

Barbara recently bought another slabstone that will occupy x consecutive regions in her garden.
She will shift the original slabstones within the garden, then place the new slabstone somewhere
in the garden. After shifting the original slabstones and placing the new slabstone, the
slabstones cannot overlap, and any two slabstones must have at least d empty regions between
them. The slabstones should remain non-overlapping during slabstone rearrangement.

Please note that, two slabstones can have less than d regions between them during slabstone
rearrangement. For example, the following process is valid when d = 2:

Shifting a single slabstone to an adjacent region takes one minute. For example, the above
rearrangement process takes 4 minutes. Now Barbara wants to know the minimum possible
total time required to rearrange the slabstones, so she can save time for “other purposes”.

9
Input Format
The first line contains four integers n, m, d and x. The i-th of the following n lines contains
two integers li and ri .

Output Format
The minimum possible total time (in minutes) to rearrange the slabstones so the new slabstone
can be placed in the garden. If the new slabstone cannot be placed in the garden no matter
how the slabstones are rearranged, just output -1.

Technical Specification
• 1 ≤ n ≤ 2000

• 1 ≤ d ≤ m ≤ 109

• 1 ≤ x ≤ m ≤ 109

• 1 ≤ li ≤ ri ≤ m for i ∈ {1, 2, . . . , n}

• ri + d + 1 ≤ li+1 for i ∈ {1, 2, . . . , n − 1}. That is, the slabstones are given in order from
left to right.

Sample Input 1 Sample Output 1

3 15 2 3 4
2 4
7 7
12 13

Sample Input 2 Sample Output 2

5 100 1 75 9
2 3
5 7
11 13
17 19
23 29

Sample Input 3 Sample Output 3

1 100 99 1 -1
1 1

10
 Problem F
Fibonacci Lucky Numbers
Time limit: 2 seconds
Memory limit: 2048 megabytes

Problem Description
Welcome to the Lucky 777 Slot Game! This game is known for its complex mathematical
challenges, where only the smartest can win the jackpot.

The slot machine is powered by a mysterious sequence—the Fibonacci sequence. But it’s
no ordinary Fibonacci sequence; it has a twist inspired by the number 7, the symbol of luck in
slot games.

When you pull the lever of the Lucky 777 Slot Machine, it generates a gigantic number
7n
using an integer n and the power of sevens: 77 . This number, however, is so massive that
even the most powerful computers cannot handle it directly.
7n
To claim the jackpot, you need to compute the last 10 digits of the F777n , the 77 -th Fibonacci
number.

Input Format
The first line contains an integer t indicating the number of test cases. Each of the following t
lines is a test case and contains exactly one positive integer n.

Output Format
For each test case, output one line contains the last 10 digits of F777n .

Technical Specification
• 1 ≤ t ≤ 20
• 1 ≤ n ≤ 109

Sample Input 1 Sample Output 1

5 1353646637
1 3172443437
2 2364206637
3 9010523437
4 9481646637
5

11
Note
The Fibonacci sequence is defined as:

• F0 = 0

• F1 = 1

• Fk = Fk−1 + Fk−2 for k ≥ 2

12
 Problem G
Game of Rounding
Time limit: 2 seconds
Memory limit: 2048 megabytes

Problem Description
Jack got a new video game called “Rounding,” which contains n levels. The game features
a global ranking system that ranks all players worldwide based on their scores. Jack wants
to break the global record and let everyone know who the master of this game is, so he has
investigated the scoring system extensively.

He finally understands the scoring rules: when a player finishes each level, they earn some
points. The player’s score is the average points they earn per level, rounded to the nearest
whole number. More precisely, if ! a player plays a total of k levels and earns p1 , p2 , . . . , pk points
k
respectively, their score will be ⌊ i=1 + 0.5⌋. For example, if a player earns [2, 3, 3] points in
pi
k
3 levels, their score will be ⌊ 3 + 0.5⌋ = 3.
2+3+3

Jack has practiced several times and knows the points ai he will earn in the i-th level. He
discovered an exploit in the game that allows him to skip some levels at the beginning and stop
at any time. This means Jack can choose a pair of numbers (l, r) where 1 ≤ l ≤ r ≤ n, and
only play the levels from l to r.

Jack is curious about the maximum score he can achieve for each starting level l for 1 ≤ l ≤ n,
and how many levels he should play to achieve that maximum score. If there are several answers
that yield the maximum score, he should print the smallest number of levels, as playing the
game for a long time is unhealthy.

Input Format
The first line contains an integer t, indicating the number of test cases. Each test case consists of
two lines. The first one contains an integer n, indicating the number of levels in the video game.
The second one contains n space-separated integers, a1 , a2 , . . . , an , representing the points Jack
will earn in each level.

Output Format
For each test case, output n integers in one line. The i-th number indicates the number of
levels Jack should play, starting from level i, to achieve the maximum score. If there are several
answers that achieve the maximum score, print the smallest number of levels.

Technical Specification
• 1 ≤ t ≤ 105

13
 • 1 ≤ n ≤ 2 × 105
• 0 ≤ ai ≤ 109 for i ∈ {1, 2, . . . , n}.
• The sum of n’s of all test cases is at most 2 × 105 .

Sample Input 1 Sample Output 1

3 2 1 1
3 4 2 2 1
1 3 3 2 1 2 1 1
4
1 2 3 4
5
2 3 2 3 3

14
 Problem H
Harmonious Passage of Magicians
Time limit: 2 seconds
Memory limit: 2048 megabytes

Problem Description
There is a very narrow alley, and two teams of magicians want to pass through this alley from
opposite ends. They do not see the other team until there is only a space that can hold one
person between the two teams. Because the alley is so narrow, they cannot turn around or
walk backward to avoid falling. However, being magicians, they can use a spell to teleport a
short distance, allowing them to pass by another person. Additionally, to maintain order, the
magicians in the same team cannot change their order, so they cannot use this spell to pass
the magician which is from the same team.

To clarify, we assume that there are n magicians in the first team, starting from the left side
and numbered from 1 to n, and m magicians in the second team, starting from the right side
and numbered from n + 1 to n + m.

The narrow alley has a total of n + m + 1 spaces. The leftmost n spaces are occupied by the
first team, facing right, and the rightmost m spaces are occupied by the second team, facing
left. The alley configuration will look like this: [1, 2, . . . , n, space, n + 1, n + 2, . . . , n + m].

When a magician moves, he must follow these rules:

• If there is an empty space directly in front of him, he can walk into that space.

• If there is a magician from the opposite team directly in front of him, and there is an
empty space directly behind this magician, he can use the spell to move to that space.

Ultimately, the first team will occupy the rightmost n spaces, and the second team will occupy
the leftmost m spaces.

To help them pass the alley, please provide a movement strategy that will allow them to pass.
The strategy will be described with a sequence of numbers a1 , a2 , . . ., where ai indicates that
in the i-th step, the magician with number ai will move to an unoccupied space.

If there are multiple strategies, please output the lexicographically smallest one. Lexicographi-
cal order is a way of comparing strings or sequences of elements based on their alphabetical or
numerical order. In the context of this problem, the “lexicographically smallest” strategy refers
to the strategy that comes first in the numerical order when the strategies are represented as
sequences of numbers.

15
More concretely:

• Each strategy is represented as a sequence of numbers: a1 , a2 , . . .

• Two strategies are compared element by element:

– If the first element of one strategy is smaller than the first element of the other, the
first strategy is lexicographically smaller.

– If the first elements are equal, compare the second elements, and so on.

Input Format
The first line contains an integer t, indicating the number of test cases. For the following t
lines, each line contains two integers n and m, indicating the number of magicians from the
first team and the number of magicians from the second team, respectively.

Output Format
Output t lines. The i-th line should contain the movement strategy that will help the magicians
pass through the narrow alley for the i-th test case. If there are multiple strategies, output the
lexicographically smallest one.

Technical Specification
• 2 ≤ n ≤ 3000
• 2 ≤ m ≤ 3000
• 1 ≤ t ≤ 1000
• The sum of n’s among all test cases is no more than 3000.
• The sum of m’s among all test cases is no more than 3000.

Sample Input 1 Sample Output 1

2 2 3 4 2 1 3 4 1
2 2 2 3 4 2 1 3 4 5 2 1 5
2 3

16
 Problem I
In Search of the Lost Array
Time limit: 2 seconds
Memory limit: 2048 megabytes

Problem Description
In a forgotten realm, a group of adventurers stumbles upon a set of mysterious scrolls hidden
deep within an ancient library. These scrolls hold the secrets of a powerful numerical array that
controls the magic of the realm. However, the scrolls have been damaged over time, and only
fragments remain. Specifically, the adventurers discover a sequence of numbers representing
the products of adjacent elements of an unknown array A.

The original array A consists of n integers a1 , a2 , . . . , an where 1 ≤ ai ≤ 100 for 1 ≤ i ≤ n. The

only information remaining on the scrolls is a sequence of n − 1 integers b1 , b2 , . . . , bn−1 , which
are unordered products of adjacent elements from A. In other words:
{b1 , b2 , . . . , bn−1 } = {a1 × a2 , a2 × a3 , . . . , an−1 × an }

Your task is to help the adventurers reconstruct one possible original array A. If there are
multiple valid arrays A that could result in the same sequence b, you may output any of them.

Input Format
The first line contains a single integer n, representing the length of the array A. The second line
contains n − 1 space-separated integers b1 , b2 , . . . , bn−1 , representing the products of adjacent
elements in the array A.

Output Format
If there is no such array A, then print No on a line. Otherwise, print Yes on the first line. Then,
output n space-separated integers a1 , a2 , . . . , an on the second line, where {b1 , b2 , . . . , bn−1 } =
{a1 × a2 , a2 × a3 , . . . , an−1 × an }.

Technical Specification
• 1 < n ≤ 18.
• 1 ≤ ai ≤ 100 for i ∈ {1, 2, . . . , n}
• 1 ≤ bi ≤ 10000 for i ∈ {1, 2, . . . , n − 1}

Sample Input 1 Sample Output 1

8 Yes
42 32 84 54 48 40 16 5 8 4 21 2 8 6 9

17
Sample Input 2 Sample Output 2
6 Yes
45 4 5 4 3 3 1 4 1 5 9

Sample Input 3 Sample Output 3

2 No
3246

18
 Problem J
Just Round Down
Time limit: 2 seconds
Memory limit: 2048 megabytes

Problem Description
The Taiwan Online Programming Contest is a prestigious event that attracts talented program-
mers from all over the world. Known for its challenging problems and competitive environment,
the contest has become a platform where only the best can prove their skills. However, there is
one problem setter who has gained a notorious reputation among participants. This problem
setter, known only by their pseudonym “truckski,” has an unusual fascination with numbers
– particularly big numbers, floating-point numbers, and any kind of mathematical challenge
that involves precise calculations. truckski has a unique style of creating problems that often
requires competitors to think carefully about the properties of numbers and how they can be
manipulated.

In this year’s edition of the Taiwan Online Programming Contest, truckski has come up with
a seemingly simple yet tricky problem. The problem revolves around a fundamental concept
in mathematics: rounding down a floating-point number to its nearest integer. While this task
might appear straightforward at first glance, truckski’s twist lies in the precision required and
the ability to handle a variety of floating-point values accurately.

Your task is to help the participants solve this problem by writing a program that takes a
positive floating-point number as input and outputs the result of rounding it down to the
nearest integer. This process is often referred to as taking the “floor” of a number. The floor
of a number is the greatest integer that is less than or equal to the number itself.

Input Format
The input consists of a single line containing one positive floating-point number x.

Output Format
The output should be a single integer, which is the floor of the input number x. Please do not
output decimal points.

Technical Specification
• 0 < x ≤ 108
• The input contains several digits and exactly one decimal point.
• The last printable character of the input must be a digit.
• There is at least one digit before the decimal point.
• There is no leading zero for x ≥ 1.

19
 • The size of input file is no more than 15 bytes.

Sample Input 1 Sample Output 1

1999.99 1999

Sample Input 2 Sample Output 2

2.00000 2

Note
The problem description is a fiction written by ChatGPT.

20
 Problem K
Kingdom’s Development Plan
Time limit: 2 seconds
Memory limit: 2048 megabytes

Problem Description
The Kingdom of Topcaria is planning a series of developmental projects to enhance its infras-
tructure. Each project has specific prerequisites that must be completed before the project can
start. The Ministry of Development has asked you to help determine a feasible order in which
all the projects can be completed.

You are given:

• n, the number of projects numbered from 1 to n.

• m, the number of prerequisite relationships between these projects.

• A list of m pairs, where each pair (a, b) indicates that project a must be completed before
project b can start.

Your task is to determine an order in which all the projects can be completed. If it is impossible
to complete all projects due to a cyclic dependency, output “IMPOSSIBLE”. If there are multiple
valid orders, please output any the lexicographically smallest one.

Input Format
The first line contains two integers n and m — the number of projects and the number of
prerequisite relationships. The next m lines each contain two integers a and b — a prerequisite
pair indicating that project a must be completed before project b.

Output Format
If it is not possible, output “IMPOSSIBLE”. If it is possible to complete all projects, output a
single line with n integers — a valid order of project completions. If there are multiple possible
orders, output the lexicographically smallest one. An order is lexicographically smaller than
another order if at the first position where they differ, the project number on the first order is
smaller than the number on the second order.

Technical Specification
• 1 ≤ n ≤ 105
• 0 ≤ m ≤ 2 × 105
• a, b ∈ {1, 2, . . . , n}
• a ̸= b

21
 • No duplicate pairs are given.

Sample Input 1 Sample Output 1

5 5 1 2 3 4 5
1 2
2 3
2 4
2 5
3 4

Sample Input 2 Sample Output 2

5 4 IMPOSSIBLE
1 2
2 3
3 1
5 4

22
 Problem L
Lexicopolis
Time limit: 2 seconds
Memory limit: 2048 megabytes

Problem Description
Welcome to Lexicopolis, the ancient city of legends and treasures. The city is famous for its
intricate network of one-way roads. There are n intersections and m one-way roads connecting
the intersections. People can only travel from intersection ui to intersection vi along road i,
and road i is associated with a magical number wi . A path of length k from intersection s to
t is a sequence of roads e1 , e2 , . . . , ek that allows travel from intersection s to intersection t. A
path is lexicographically smaller than another path if at the first road where they have different
magic numbers (not index), the number on the first path is smaller than the number on the
second path.

It is rumored that the tourist who figures out the lexicographically smallest path of length k
from intersection s to intersection t can receive a gift from the Lexicopolis government. Please
write a program to find the lexicographicall smallest path of length k from intersection s to t.
If it is impossible to travel from intersection s to t with exactly k roads, output -1.

Input Format
The first line contains six integers n, m, s, t, x, k. n is the number of intersections. m is the
number of roads. s is the starting intersection and t is the ending intersection. x is a number
that will be used for outputting the answer. k is the length of path. The i-th of the m
following lines contains three integers ui , vi and wi . That means road i is from intersection ui
to intersection vi and associated with magic number wi .

Output Format
If there is no path of length k from intersection s to t, output -1. Otherwise, assume such a
!
path exists. Consider the lexicographically smallest path e1 , e2 , . . . , ek , and output ki=1 wei xk−i
modulo 109 +7, where x is the number provided as the fifth value in the first line of the input.

Technical Specification
• 2 ≤ n ≤ 50
• 1 ≤ m ≤ n2 − n
• 1 ≤ ui ≤ n for i ∈ {1, 2, . . . , m}
• 1 ≤ vi ≤ n for i ∈ {1, 2, . . . , m}
• 1 ≤ wi ≤ 109 for i ∈ {1, 2, . . . , m}
• ui ̸= vi for i ∈ {1, 2, . . . , m}

23
 • (ui , vi ) ̸= (uj , vj ) for i ̸= j
• 1≤s≤n
• 1≤t≤n
• 1 ≤ k ≤ 109
• 1 ≤ x ≤ 109

Sample Input 1 Sample Output 1

3 6 1 3 10 4 1211
1 2 2
2 1 1
1 3 1
3 1 2
2 3 1
3 2 2

Sample Input 2 Sample Output 2

3 6 1 3 10 5 12121
1 2 2
2 1 1
1 3 1
3 1 2
2 3 1
3 2 2

Sample Input 3 Sample Output 3

6 7 5 6 10 10 121513477
1 2 1
2 4 2
3 4 1
4 5 3
5 3 5
4 6 2
6 5 1

Sample Input 4 Sample Output 4

6 7 1 6 123 2 -1
1 2 1000000000
2 4 2

24
3 4 3
4 5 4
5 3 1
4 6 2
6 5 1

25