Noah loves music and has various albums stored on discs. However, whenever he listens to his albums, he is very picky about the songs and skips around a lot. The disc always starts on the first song and rotates in order of the album. Once it gets past the end, it restarts from the beginning. Given how many songs Noah skips before listening to each song, print the list of songs in the order he listened to them.

Note: Whenever he decides on a song, he listens to it in its entirety before counting his skips to the next song.

Tommy is cataloging records in her music shop. She wants to arrange them onto a 1-dimensional shelf by record matrix number, but some of the ink has been scratched off. Given $$$n$$$ disks labeled $$$1$$$ to $$$n$$$, she has deduced the following $$$k$$$ relationships: in the $$$i$$$th relationship, she knows that two disks $$$a_i$$$ and $$$b_i$$$ are adjacent to each other. It is guaranteed that each unordered pair $$$(a_i, b_i)$$$ of disks is distinct. Given these $$$k$$$ conditions, determine how many ways she can catalog the disks mod $$$10^9+7$$$.

After many years of songwriting and practicing, the up-and-coming UTBC (UT Beats Club) is finally ready to debut! In order to do so, they must choose some of their songs to record for their debut album.

Currently, they have written a total of $$$n$$$ songs, each with their own excitement level. The list of songs can be represented by an array $$$a$$$, where the $$$i$$$-th song in the array has an excitement level of $$$a_i$$$. In order for their album to be thematically coherent, UTBC has decided they want to choose a subarray$$$^†$$$ of songs from $$$a$$$ to put on the album.

UTBC doesn't want their debut to be a flop, so they want to choose which songs they put on their record album carefully. After extensive market research, they have discovered that audiences love an album that contains a song that stands out. In particular, a record album is considered noteworthy if it contains a song whose excitement level is strictly greater than the sum of the excitement levels of all the other songs on the album. For example, [3, 1, 1] is noteworthy because $$$3 \gt 1+1$$$, whereas [2, 2] and [1, 2, 3] are not.

Now UTBC wants to know, given the array $$$a$$$ of their songs, how many different possible noteworthy record albums could they produce as their debut album? Help them calculate this answer before they debut!

$$$^†$$$A subarray of $$$a$$$ is defined as a sequence of consecutive elements of $$$a$$$, i.e. the array $$$a_i,a_{i+1},\dots,a_j$$$ for some $$$1\leq i\leq j\leq n$$$.

Michael's favorite artist, Jackson, has recently started releasing new songs at an unprecedented rate. Michael wants to collect a physical copy of every record this artist releases, but his collection is getting too big. He already knows how many songs the artist releases over the first $$$n$$$ days, and wonders how many records he will have to buy on day $$$k$$$ if he continues to purchase every record.

Michael uses the function $$$f(x)$$$ to estimate the number of records released on day $$$x$$$. Michael already knows $$$f(x)$$$ for $$$1 \leq x \leq n$$$ as mentioned above. To compute future estimates, Michael uses the formula

Given the values of $$$f(x)$$$ for $$$1 \leq x \leq n$$$, help Michael calculate his estimate $$$f(k)$$$, modulo $$$10^9 + 7$$$.

Vinny is having guests over for dinner, and wants to play some music to accompany her famed vindaloo. Vinny is, of course, an avid fan of old-school vinyls and cassettes, and owns a collection of songs in her attic.

Unfortunately, the attic doesn't have any lights, so Vinny can't find what she needs! Vinny is holding an object, but she can't tell what it is. She has identified $$$10$$$ points $$$(x_i, y_i)$$$ on the boundary of the object. If it's a vinyl, the object boundary is a circle. If it's a cassette, the object boundary is a rectangle. What is Vinny holding?

George was perusing the local album store when he received an urgent message: a club was handing out free lollipops on Speedway! Determined to take advantage of such an opportunity, George decided to escape the album store as quickly as possible.

He found himself in row $$$n$$$ and column $$$m$$$, the southeast corner of the store, and wants to get to row $$$1$$$ column $$$1$$$, the exit in the northwest corner. In this store, each grid cell in row $$$i$$$ and column $$$j$$$ has a record of value $$$r_{i,j}$$$. When George takes a step in a direction, he considers shopping more and pauses for a time equal to the square of the sum of record values that are in front of him along the row or column in which he moved. For example, if George is in position $$$(i, j)$$$ and takes a step to position $$$(i - 1, j)$$$, he waits a time equal to $$$(\sum^{i-2}_{q=1} r_{q,j})^2$$$. Likewise, if he takes a step to position $$$(i, j - 1)$$$, he waits a time equal to $$$(\sum^{j-2}_{q=1} r_{i,q})^2$$$. George can move only towards the exit, so he can move only north or west.

What's the minimum time in which George can exit the album store?

John is making $$$n$$$ records and he knows of $$$m$$$ unique songs. Each record must contain exactly one song. Further, each record has a value $$$b_i$$$ denoting that if the $$$i$$$th record is played, the $$$b_i$$$th record must be played next. John can assign any song to any record (there may be multiple records with the same song, or a song that isn't on any record), but each record must be assigned exactly one song. However, he wants to make sure that anyone who plays his records will not end up listening to the same song twice.

Formally, let $$$a_i$$$ be the song assigned to the $$$i$$$th record. For all $$$i$$$, $$$a_i \neq a_{b_i}$$$ must hold. Help John determine how many assignments of songs to records satisfy this condition. Two assignments are considered different if there is a record which has a different song assigned to it between the two assignments. Since this value may be large, output it modulo $$$10^9+7$$$.

Charlie is writing a mixing software, which takes in an array of records $$$a$$$ with $$$n$$$ elements. Charlie also wants to mix the tracks together. He has devised this clever algorithm (that also produces great soundtracks) called the prefix mixing operation $$$p(a)$$$ as follows:

• $$$a[i] := a[i - 1] \times a[i]\bmod {10^9 + 7}$$$, for each $$$1 \lt i \leq n$$$ in order.

For example, for the array $$$a = [5,7,10]$$$, the prefix operation would produce $$$p(a) = [5,35,350]$$$, since the multiplication is done in succession. The $$$k$$$-th prefix operation $$$p^{k}$$$ is the prefix operation applied $$$k$$$ times. For example, for $$$k=2$$$, $$$p^{2}(a)$$$ would be defined as $$$p(p(a))$$$, and $$$p^{3}(a) = p(p(p(a)))$$$.

Unfortunately, the current software rendering this transformation takes a long time to run, so Charlie needs your help to fix it. In order to do this, Charlie wants to know arbitrary elements for the array $$$p^{k_i}(a)$$$. Can you help him find them?

Amber wants to store her favorite songs on a vinyl record!

Amber's record can store $$$m$$$ bytes of data (it's a fancy digital record), and Amber has $$$n$$$ songs which she wants to store. Each of the $$$n$$$ songs has a title $$$s_i$$$, and it takes $$$|s_i|$$$ bytes to store the $$$i^\text{th}$$$ song. Additionally, Amber values different songs differently, so she assigns a value $$$v_i$$$ to the $$$i^\text{th}$$$ song. Moreover, Amber does not mind listening to the same song multiple times; that is, she may store the same song multiple times on her vinyl, and each time she stores the $$$i^\text{th}$$$ song, it will add the value $$$v_i$$$ to the total value of the record.

Amber would like to maximize the total value of the songs she stores on her digital vinyl. Given the size of her vinyl (in bytes), as well as the titles and values of each of her favorite songs, please help Amber figure out the maximum total value she can achieve by storing the optimal songs!

Bob has just bought a record collection of $$$n$$$ records numbered from $$$1$$$ to $$$n$$$, and he can't wait to listen to them! On each of the next $$$n$$$ days, Bob will listen to some his records. He may listen to the same record multiple times, or on different days. A new record is a record that he has not listened to on previous days. Bob is very excited to start listening to his record collection, and he wants to know, what is the greatest number of new records he listens to in a single day? Help him answer this question!

As a music producer, Mai has been trying to get her career off the ground! She has $$$n$$$ samples on a record disk. The disk is represented as a string $$$s$$$ of $$$n$$$ characters, where each sample is labeled with some lowercase character 'a'-'z'. As part of creating a beat, Mai will pick some substring of samples to use as the foundation of their beat. Mai prefers sounds that have a symmetric sound to them, so the substring she extracts must be a palindrome.

The heat of a substring of samples is the sum of the IDs used, where 'a' corresponds to a value of 1, 'b' corresponds to a value of 2, and so forth. If an ID appears multiple times, it is counted multiple times in this sum. Mai wants to compute how valuable the record is, so she wants to compute the sum of the heats of all distinct valid substring of samples. Please help her do so!

A palindrome is a string that reads the same forwards and backwards. For example, "aa" and "abacaba" are both palindromes, while "abb" and "utpc" are not.

Two substring are distinct if they have different lengths or at least one position differs between the two substring.

Alice and Bob are tired of listening to records all day, so they decided to get food. Of course there is no better place to get food than at the Unlimited Topping Pizza Cafe (UTPC).

At the UTPC, every pizza is represented by a set of toppings arranged in a circle. Specifically, there are $$$n$$$ positions on the pizza, numbered from $$$1$$$ to $$$n$$$. Each topping has a tastiness value in the range $$$[1, 100]$$$, and each position on a pizza may contain up to two toppings (possibly none). It is well-known that if two toppings line on the same position of a pizza, they will no longer have any tastiness, so the tastiness of a pizza is defined as the sum of tastiness of all toppings on the pizza which do not share a position with any other topping.

This is both Alice's and Bob's first time visiting the UTPC, and they have a dilemma: They each have a pizza in mind (which contains at most one topping at each position), but can only afford to purchase one (the pizzas here are quite expensive). You, the chef, know how to solve the dilemma: by merging the two pizzas into one! First, you will rotate Bob's pizza by some amount so that each position in Bob's pizza is aligned with some position in Alice's pizza. Then, you will transfer all of Bob's toppings to the corresponding position on Alice's pizza. Since you want Alice and Bob to return in the future, you must find the maximum tastiness which a pizza can contain after merging Alice's and Bob's pizzas.