The UTPC officers have planned an exciting transcontinental road trip across the United States! They begin their journey in the vibrant city of San Francisco.
While in Fisherman's Wharf, Aaryan stumbled upon a fishy tank. He wants to remember this moment vividly, but because the UTPC officers forgot to bring a camera, he can't take a picture. He has thus come to you to ask for a drawing of the fishy tank.
The fishy tank has $$$n$$$ fishies. An empty tank can be displayed by a $$$15$$$ by $$$25$$$ grid of '-', 'o', '|', and space characters, as shown in the sample test cases.
Aaryan wants you to draw the fish tank with $$$n$$$ fishies in it. Each fishy is represented by the sequence of characters '><>' (facing right) or the sequence '<><' (facing left). The fishies can appear anywhere as long as each fishy doesn't overlap with any other fishy or the border of the grid. There is no restriction on which direction the fishies must be facing. Aaryan will be happy if the drawing consists of exactly $$$n$$$ fishies. Please make Aaryan happy!
The input will consist of a single integer $$$n$$$ ($$$1 \leq n \leq 10$$$) — the number of fishies in the tank.
Output $$$15$$$ lines, each containing a string of length $$$25$$$, representing the drawing that you have made for Aaryan.
2
o-----------------------o | | | | | | | <>< | | | | ><> | | | | | | | | | | | | | | | o-----------------------o
5
o-----------------------o | | | <>< | | | | | | ><> ><> | | | | ><> | | | | | | | | | | | | ><> | o-----------------------o
The officers stop in Las Vegas, a city known for its magic shows and card games!
Equipped with a fresh deck of cards from the magic shop, the officers decide to play a game. They have a deck with a permutation of $$$n$$$ cards, numbered from $$$1$$$ to $$$n$$$. They will draw cards one at a time, and keep track of their score in the following way:
On the $$$i$$$-th draw, an officer will draw the card with number $$$c_i$$$. For every card in the (initially empty) discard pile, if the card's number is greater than $$$c_i$$$, that officer will add $$$c_i + k$$$ to their score, where $$$k$$$ is the value of the card. Finally, the officer adds card $$$c_i$$$ to the discard pile.
The officers will repeat this process until the deck is empty. Can you help them calculate what their final score will be?
The first line contains an integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ — the number of cards in the deck.
The next line contains $$$n$$$ integers $$$c_1,c_2\dots,c_n$$$ $$$(1 \leq c_i \leq n)$$$ — the cards of the deck in the order in which they were drawn.
Output a single integer, the score the officers will end with.
31 2 3
0
51 4 2 3 5
13
For the first test, the card with number 1 is drawn, then card 2, then card 3. No card in the discard pile is ever greater than a drawn card, so the score is 0.
For the second test, the officers increases their score by (4+2) when they draw the card numbered with a 2, and the officers increase their score by (3+4) when they draw the card numbered with a 3. Thus, their final score is 13.
The UTPC officers have arrived in Albuquerque just in time for the annual balloon fiesta! They have finally purchased a camera so that they can take photos of the balloons.
The balloons are just about to take off, and $$$n$$$ of them are currently arranged in a row, numbered from $$$1$$$ to $$$n$$$ in left to right order. By chance, each balloon consists of a single color that is represented by a lowercase English letter, and the entire row of balloons is represented by a string $$$s$$$ of length $$$n$$$. Moreover, the $$$i$$$-th balloon consists entirely of the color $$$s_i$$$, and if two balloons have the same color, they appear identical.
Mark has taken $$$q$$$ photos, each of a subsequence of consecutive balloons. The $$$j$$$-th photo is represented by $$$l_j$$$ and $$$r_j$$$, indicating that the $$$j$$$-th photo is the substring $$$s[l_j...r_j]$$$ where $$$s[a...b]$$$ denotes the substring of $$$s$$$ from index $$$a$$$ to index $$$b$$$ (both inclusive). Dylan took a single photo of the entire row of balloons.
The following day, Dylan is viewing Mark's photos and for each one he is curious as to how many of the $$$n$$$ balloons could have been in the photo. Balloon $$$i$$$ could be in the $$$j$$$-th photo if index $$$i$$$ is contained in a substring of $$$s$$$ that is equal to $$$s[l_j...r_j]$$$. More formally, balloon $$$i$$$ could be in the photo if there exists $$$a \in [1, n + l_j - r_j]$$$ such that $$$s[a...a+r_j-l_j] = s[l_j...r_j]$$$, and $$$a \leq i \leq a + r_j - l_j$$$. Please help Dylan, and for each of Mark's photos, output the number of balloons that could have appeared in the photo!
The first line of input consists of integers $$$n$$$ and $$$q$$$ ($$$1 \leq n, q \leq 2 \cdot 10^5$$$) — denoting the number of balloons in the row and the number of photos taken by Mark respectively.
The second line of input consists of a string $$$s$$$ of $$$n$$$ lowercase English characters, where $$$s_i$$$ denotes the color of the $$$i$$$-th balloon in the row.
The $$$j$$$-th of the next $$$q$$$ lines consists of integers $$$l_j$$$ and $$$r_j$$$ ($$$1 \leq l_j \leq r_j \leq n$$$) — denoting the leftmost and rightmost balloons included in the $$$j$$$-th of Mark's photos.
Output $$$q$$$ integers each on their own line, representing the number of balloons that could have appeared in each of Mark's photos.
12 3abcabbcababa1 27 98 10
8 6 5
The first photo that Mark took is $$$s[1...2] = \text{ab}$$$. The $$$8$$$ balloons that could appear in the photo are balloons $$$1$$$ (in $$$s[1...2]$$$), $$$2$$$ (in $$$s[1...2]$$$), $$$4$$$ (in $$$s[4...5]$$$), $$$5$$$ (in $$$s[4...5]$$$), $$$8$$$ (in $$$s[8...9]$$$), $$$9$$$ (in $$$s[8...9]$$$), $$$10$$$ (in $$$s[10...11]$$$), and $$$11$$$ (in $$$s[10...11]$$$).
The second photo that Mark took is $$$s[7...9] = \text{cab}$$$. The $$$6$$$ balloons that could appear in the photo are balloons $$$3$$$ (in $$$s[3...5]$$$), $$$4$$$ (in $$$s[3...5]$$$), $$$5$$$ (in $$$s[3...5]$$$), $$$7$$$ (in $$$s[7...9]$$$), $$$8$$$ (in $$$s[7...9]$$$), and $$$9$$$ (in $$$s[7...9]$$$).
The third photo that Mark took is $$$s[8...10] = \text{aba}$$$. The $$$5$$$ balloons that could appear in the photo are balloons $$$8$$$ (in $$$s[8...10]$$$), $$$9$$$ (in $$$s[8...10]$$$), $$$10$$$ (in $$$s[8...10]$$$ and $$$s[10...12]$$$), $$$11$$$ (in $$$s[10...12]$$$), and $$$12$$$ (in $$$s[10...12]$$$).
The group has arrived in Austin! There they discover that the city council needs their help. However, they are very busy attending concerts so they've asked you to do this for them!
The city council of Austin is planning a large-scale urban renewal project along its East–West highway. There are $$$n$$$ proposed building expansions, each located at a distinct integer coordinate along the highway. Every proposal has an associated profit value. However, due to zoning regulations, any two chosen expansions must be sufficiently far apart. Specifically, if you approve the expansion at coordinate $$$x$$$, then you may not approve another expansion within distance $$$d$$$ of $$$x$$$.
Formally, you are given:
The first line contains two integers $$$n$$$ and $$$d$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq d \leq 10^9$$$).
Each of the next $$$n$$$ lines contains two integers $$$x_i$$$ and $$$p_i$$$ ($$$1 \leq x_i \leq 10^9$$$, $$$1 \leq p_i \leq 10^9$$$).
It is guaranteed that all $$$x_i$$$ are distinct.
Print a single integer: the maximum total profit you can achieve while respecting the spacing constraint.
6 23 15 47 18 29 112 5
12
There is a house in New Orleans...
In fact, upon arriving in the city, the UTPC officers discover that there are many houses in New Orleans. But before even taking a single step, they are accosted by the mayor, who has heard of a certain geniosity among the group that can solve any problem. The problem he needs help with is thus:
The city of New Orleans can be represented as a 2D plane with $$$n$$$ houses located at different integer points along the plane. The city is planning on laying a new set of fiber-optic cables to service these houses, which will be built as a straight line on the plane. Because the mayor wants everyone to be close to the cable, he cares about the furthest distance that a house will be from the line of cable. There have been $$$q$$$ proposals for different lines, and so the mayor requests the assistance of the group to compute this value for each proposed line in order to figure out which plan is the best.
The group is eager to explore the rich history, live music, and famous cuisine of the city, so help them answer the mayor's queries as fast as possible so they can get back on track!
The first line of input contains two integers $$$n$$$ and $$$q$$$ ($$$1 \leq n,q \leq 2\cdot10^5$$$) — the number of houses and number of proposals.
The next $$$n$$$ lines contain two integers $$$x_i$$$ and $$$y_i$$$ ($$$|x_i|,|y_i| \leq 10^9$$$) — the coordinates of the $$$i$$$th house. It is guaranteed that no two houses share the same coordinates.
The next $$$q$$$ lines contain three integers $$$A_i, B_i, C_i$$$ ($$$|A_i|, |B_i|, |C_i|\leq 10^9$$$) — specifying the $$$i$$$th proposal is for a line with the equation $$$A_ix + B_iy + C_i = 0$$$. It is guaranteed that either $$$A_i$$$ or $$$B_i$$$ is nonzero.
For each proposal, output the furthest distance a house has from the line. Your answer will be considered correct if its absolute or relative error doesn't exceed $$$10^{-6}$$$.
2 20 01 1-1 1 01 1 -2
0.0000000000 1.4142135624
In the first test, there are houses at (0,0) and (1,1). The first proposal is the blue dotted line, which runs through both houses, so it has a maximum distance of 0 from any house. The second proposal is the green dotted line, and it is furthest from the house at (0,0), with a distance of sqrt(2).
After a long night of partying in Atlanta, Michael needed to get back to his hotel to meet with the rest of the officers. Luckily, MagiCorp's CEO, Magikarp, decided to deploy their driverless car system, Laymo, to Atlanta just a few days ago. Seeing this opportunity to try this out for himself, Michael called one, hoping to get a smooth ride back. However, the confusing road layouts have gotten Laymo's cars a little confused. Instead of driving regularly, all the Laymo cars now drive randomly.
The streets of Atlanta can be modeled as a graph with nodes representing intersections and edges representing two-way streets between different intersections, where the $$$i$$$-th street takes $$$t_i$$$ minutes to drive through. In total, there are $$$n$$$ intersections and $$$m$$$ streets. There can be more than 1 street between a pair of intersections.
Currently, Michael is at intersection $$$1$$$, and his hotel is at intersection $$$n$$$. Initially, his Laymo will choose a road connected to intersection $$$1$$$ uniformly at random and drive in that direction. Upon reaching the next intersection, the Laymo will again choose a road connected to that intersection uniformly at random to drive through (including the road that the Laymo just came from). This process repeats until Michael reaches his hotel, in which case he steps out of the car and stops travelling. If an intersection has no roads connected to it, the Laymo will simply stop where it is.
After $$$k$$$ minutes have passed, what is the probability that Michael will be back at the hotel with the UTPC team?
The first line contains $$$n$$$, $$$m$$$, and $$$k$$$ $$$(2\leq n\leq 50, 0\leq m\leq 10^5, 1\leq k\leq 10^6)$$$ — the number of intersections, the number of streets, and the number of minutes.
The next $$$m$$$ lines contain 3 integers $$$u_i$$$, $$$v_i$$$, and $$$t_i$$$, denoting two intersections connected by a street that takes $$$t_i$$$ minutes to drive through $$$(1\leq u_i,v_i\leq n, 1\leq t_i\leq 5, u_i\neq v_i)$$$.
Output a single integer, the probability that Michael will be at the hotel after $$$k$$$ minutes, modulo $$$10^9+7$$$.
Formally, let $$$M=10^9+7$$$. It can be shown that the exact answer can be expressed as an irreducible fraction $$$\frac{p}{q}$$$, where $$$p$$$ and $$$q$$$ are integers and $$$q\not\equiv 0 \pmod{M}$$$. Output the integer equal to $$$p\cdot q^{-1} \bmod{M}$$$. In other words, output such an integer $$$x$$$ such that $$$0\leq x \lt M$$$ and $$$x\cdot q\equiv p \pmod{M}$$$
3 3 21 2 12 3 21 3 1
500000004
4 3 41 2 11 3 51 4 1
444444448
For the first test case:
At the start of the first minute, Michael goes to intersection 3 (the hotel) with probability $$$\frac{1}{2}$$$ and intersection 2 with probability $$$\frac{1}{2}$$$, and each road takes a minute to travel.
At the start of the second minute, Michael could be at the hotel, in which he exits the Laymo and stops traveling, or at intersection 2. If he is at intersection 2, Michael will go towards intersection 1 with probability $$$\frac{1}{2}$$$ and the hotel with probability $$$\frac{1}{2}$$$. However, the road to the hotel takes 2 minutes, so he will not reach the hotel in time by the end of the second minute.
In total, Michael has a $$$\frac{1}{2}$$$ probability of getting to his hotel. This is equivalent to $$$500000004$$$ (mod $$$10^9+7$$$).
During their stop in Nashville, the UTPC officers decide to attend a country music concert.
At the concert, a group of musicians have lined up, each hoping to perform. However, they are having some trouble deciding on the exact roster, and the organizers of the concert want the officers' help!
To make it easier for the organizer, the officers can only pick some contiguous subarray of the musicians. Each musician has some associated ability, an integer describing how well they can play music. The musicality of a roster of musicians is the median ability in the set. Here, the median of a list of numbers, if written as $$$a_1, a_2, \dots, a_m$$$ in sorted order, is $$$a_{\left\lceil \frac{m + 1}{2} \right\rceil}$$$.
Out of all the possible rosters, the organizers want to find the $$$k$$$-th smallest musicality. Could you help them find this value?
The first line contains two integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 10^5, 1 \leq k \leq 10^{10}$$$) — the number of artists in line and the desired smallest musicality, respectively. It is guaranteed that there are at least $$$k$$$ possible rosters.
The following line contains $$$n$$$ space-separated integers $$$a_1, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — the ability of the $$$i$$$-th artist.
Output the $$$k$$$-th smallest musicality possible from all the possible rosters.
4 34 2 3 1
2
For the sample:
Putting these in order, we get $$$1, 2, 2, 3, 3, 3, 3, 3, 4, 4$$$ as the possibilities for the medians. Thus, the third index is $$$2$$$.
On their stop in Chicago, the UTPC officers have decided to visit the Art Institute of Chicago.
One of the most famous paintings at the Art Institute of Chicago is A Sunday Afternoon on the Island of La Grande Jatte, by Georges Seurat, shown above. The painting is most well-known for its use of pointillism, whereby small dots of color blend together to enhance the painting's vibrancy. Inspired by this artwork, Edward invented his own technique known as Lineism, which uses horizontal and vertical strokes to paint lines that are 1 pixel wide and arbitrarily long.
Edward would like to paint every pixel of a shape that is convex, which means any horizontal or vertical stroke between two pixels in the shape lies entirely within the shape. The shape is also connected, which means there is a path between any two pixels in the shape using only vertical and horizontal movements within the shape. The shape is represented by an $$$n \times m$$$ grid of characters, where an 'X' denotes a pixel to paint and a '.' denotes a blank pixel that should remain unpainted.
Edward is currently busy preparing for a diamond heist, so he needs help to find the minimum number of strokes required to fill in the shape. Note that a pixel can be painted by multiple strokes.
The first line of input contains $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 200$$$), the number of rows and columns in the shape, respectively.
The next $$$n$$$ lines each contain a string of length $$$m$$$, consisting of only the characters 'X' and '.', representing a row in the grid.
The output should be a single integer, the minimum number of strokes required to paint every pixel of the given shape.
5 5..X...XXX.XXXXX.XXX...X..
4
George can paint the 3rd row and the 2nd, 3rd, and 4th columns. It can be proven that 4 is the minimum number of strokes needed to fill in the shape.
The UTPC officers have arrived in Cincinnati! As avid tennis fans, they are very excited to watch the Cincinnati Masters 1000 tournament, the lead up event to the last grand slam of the year, the US Open.
One of the top players in the event, Carlos Alcaraz, is about to warm up for his first match. As part of the warmup, his coach, Juan Carlos Ferrero, has challenged him to a play a game that will stimulate his mind.
In this game, there are $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ piles of tennis balls, where the $$$i^\text{th}$$$ pile has $$$a_i$$$ balls. In one operation, Alcaraz adds the $$$\mathrm{MEX}^\dagger$$$ of the current pile sizes to his score and then chooses any pile and removes a single tennis ball from it. He keeps doing these operations until every pile is empty (has 0 balls). Alcaraz's goal is to maximize his score after all operations have taken place.
Watching Alcaraz play the game, the UTPC officers now wonder, what is the maximum score Alcaraz can achieve? Help Alcaraz maximize his score!
$$$^\dagger$$$The $$$\mathrm{MEX}$$$ (minimum excluded value) of an array is the smallest non-negative integer that is not in the array. For example:
The first line contains an integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$ — the number of piles.
The next line contains $$$n$$$ numbers, $$$a_1, a_2, \dots, a_n$$$ $$$(0 \leq a_i \leq 10^6)$$$ — the number of tennis balls in each pile. Note that a pile can be empty to start.
Output a single number, the maximum score Alcaraz can achieve.
30 1 3
9
53 1 5 6 4
54
In the first test case, one sequence of operations Alcaraz can use is:
$$$[0, 1, 3]$$$ -> $$$[0, 1, 2]$$$ -> $$$[0, 1, 1]$$$ -> $$$[0, 1, 0]$$$ -> $$$[0, 0, 0]$$$
The MEX to start is 2. The MEX of the pile sizes after the operation sequence above is $$$3, 2, 2, 1$$$ in that order. Note that the MEX of $$$[0, 0, 0]$$$ is NOT added to the final answer, as no more operations can be done to remove tennis balls from any pile.
The score for this sequence of operations is $$$2 + 3 + 2 + 2 = 9$$$. It can be proven that this is the maximum score Alcaraz can achieve.
The group is welcomed to the nation's capital, Washington D.C.!
The city is home to the greatest collection of museums in the world. One museum, the Smithsonian Museum of Natural History, houses the Hope Diamond, one of the largest diamonds in the world, worth >200 million USD.
To keep the diamond safer, the Smithsonian is considering new floorplans for the museum. A floorplan can be described as a collection of $$$n$$$ rooms connected by $$$m$$$ one-way doors. Each one-way door requires a certain access-level to go through in one direction, and is impossible to go through in the other direction. Each person visiting the museum (visitors and employees) have keycards giving them some constant access-level. If their keycard grants them access level $$$k$$$, they can go through all one way doors requiring $$$ \leq k $$$ access-level. The only entrance/exit to the museum is at room $$$1$$$.
We call a museum floorplan foolproof if it is not possible to get stuck in the museum. Specifically, it is possible to get stuck in the museum if there exists an access-level $$$k$$$ such that a person with access-level $$$k$$$ could reach a room in the museum from room 1 for which it is impossible to return to room 1 with access-level $$$k$$$.
Please determine if the given floorplan is foolproof!
The first line contains integers $$$n, m$$$ ($$$1 \leq n, m \leq 10^5$$$) — the number of rooms and the number of hallways.
The $$$i$$$-th of the next $$$m$$$ lines contains three integers, $$$a_i, b_i, c_i$$$ ($$$1 \leq c_i \leq 10^9, 1 \leq a_i, b_i \leq n, a_i \neq b_i$$$) specifying that there is a one-way door leading from room $$$a_i$$$ to room $$$b_i$$$ requiring access-level $$$c_i$$$.
For each pair of rooms $$$x$$$ and $$$y$$$ it is guaranteed that there is at most one one-way door from room $$$x$$$ to room $$$y$$$. Note that there can exist both a door from $$$x$$$ to $$$y$$$ and from $$$y$$$ to $$$x$$$.
Output one word, "YES" or "NO", answering whether the given floorplan is foolproof.
4 51 2 12 4 24 3 22 3 13 1 1
YES
4 51 2 22 3 33 4 44 1 54 2 1
NO
The UTPC officers have arrived in Philadelphia, and have stumbled upon Kuroni and Tfg! They offered to help test the upcoming UTPC contest, but only if you solve their problem:
Kuroni and Tfg have arrived at the famous Philadelphia Museum of Art! On their map, they've marked the rooms they're most excited to see, from the grand Armor Court to the hidden Japanese Teahouse. Interestingly, the museum's layout is a tree, meaning it's possible to reach every room from the entrance and there are no cycles. Unfortunately, their time is limited, so they're unsure how to plan their route. Kuroni and Tfg each want to maximize their their own score, which is the number of rooms they had marked on their map that they ended up visiting.
To make things fair, they agree on the following rules:
When someone is choosing the next room, they will choose the room that maximizes their eventual final score. If there multiple such rooms, they will choose the rooms that maximizes the other's eventual final score. Given their preferences and the museum's layout, determine each of their scores!
The first line contains an integer $$$n$$$ ($$$1 \le n \le 10^5$$$), the number of rooms.
The second line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$, where $$$a_i$$$ is $$$1$$$ if Kuroni likes room $$$i$$$, and $$$0$$$ otherwise.
The third line contains $$$n$$$ integers $$$b_1, b_2, \dots, b_n$$$, where $$$b_i$$$ is $$$1$$$ if Tfg likes room $$$i$$$, and $$$0$$$ otherwise.
The next $$$n-1$$$ lines each contain two integers $$$p$$$ and $$$q$$$ ($$$1 \le p,q \le n$$$), representing a connection between rooms $$$p$$$ and $$$q$$$ on the map. It is guaranteed that the edges form a tree.
Output two integers $$$x$$$ and $$$y$$$ — the number of rooms Kuroni likes and the number of rooms Tfg likes, respectively, in the final route they take according to the rules.
50 1 1 0 10 0 1 1 11 21 32 42 5
2 1
In the sample, Kuroni will first choose to go from room $$$1$$$ to room $$$2$$$, visiting one of her marked rooms. Tfg will then go, choosing room $$$5$$$ so both of them visit a room they marked. Since they can't go back to room $$$2$$$ they are finished, with Kuroni visiting $$$2$$$ preferred rooms, and Tfg $$$1$$$.
The road trip has now stopped in New York City, and it appears Walrus has snuck away at a pit stop! As usual, Walrus is scouting for places to create shrines. This time, he has met up with Kimmy in Central Park to build a Chaewon shrine. While looking for open space in Sheep Meadow, Walrus steps on a hidden tile that collapses below him, trapping him hundreds of feet under the park.
He is met by an ancient spirit who tells Walrus the following:
"In front of you are $$$n$$$ crates, numbered from $$$1$$$ to $$$n$$$, which all need to be filled with some number of apples. For crate number $$$i$$$, you need to place $$$\operatorname{lcm}(i, n)$$$ apples into that crate. If any crate has too few or too many apples, toxic fumes will enter the room and you will meet your peril. You need not worry about gathering these apples, however. Simply input the number of apples you will need in total (modulo $$$10^9 + 7$$$) into the machine on your right, and the machine will take care of the apples (or disperse the fume)."
Help Walrus avoid his peril! Given $$$n$$$, calculate $$$\sum_{i=1}^n \operatorname{lcm}(i, n)$$$, modulo $$$10^9 + 7$$$.
The only input will be $$$n$$$ ($$$1 \le n \le 10^{12}$$$) — the number of crates.
Output the number of apples needed, modulo $$$10^9 + 7$$$.
4
24
6
66
In the first sample, the $$$4$$$ crates will have $$$4$$$, $$$4$$$, $$$12$$$, and $$$4$$$ apples.
In the second sample, we have crates labeled from $$$1$$$ to $$$6$$$. Respectively, these will have $$$6$$$, $$$6$$$, $$$6$$$, $$$12$$$, $$$30$$$, and $$$6$$$ apples.
After the UTPC officers arrived in their final stop at Boston, Randy decides to participate in the annual Boston Tea Party, where he will be dumping boxes of tea into the Boston harbor.
Currently, Randy has $$$n$$$ boxes of tea lined up to be dumped, with the $$$i$$$th box weighing $$$w_i$$$ pounds. On the $$$i$$$th second after the party has commenced, Randy can either dump the $$$i$$$th box into the harbor or choose not to do anything.
Since the organizers of the party are concerned about the environmental consequences of dumping tea, they have imposed the following restriction: At any given moment, the amount of tea a person can dump cannot exceed $$$t^2$$$ pounds in total (since the party started), where $$$t$$$ is the number of seconds after the party has begun.
As Randy wants to be well prepared for this momentous event, he would like to know the number of ways he can dump tea into the harbor without violating the party rules. Two ways of dumping tea are considered distinct if there exists a box that was dumped in one way but not the other.
The first line contains $$$n$$$ $$$(1 \le n \le 10^5)$$$ — the number of tea boxes Randy has.
The second line contains $$$n$$$ integers $$$w_1, w_2,\dots,w_n$$$ $$$(0 \le w_i \le 10^5)$$$ — the weights of the boxes. It is guaranteed that $$$\sum_{i=1}^n w_i \le 10^5$$$.
Output a single integer, the number of ways Randy can dump tea into the harbor. Since the answer may be large, output it modulo $$$10^9 + 7$$$.
21 4
3
33 3 3
4
In the first test case, Randy can dump tea into the harbor in three ways:
In the second test case, Randy can dump tea into the harbor in four ways: