Problem Statement

Takahashi is designing a system that transmits a signal through N repeaters as part of a communications engineering experiment.

The signal is emitted from Takahashi's transmitter and is transmitted sequentially to the 1-st repeater, the 2-nd repeater, ..., and the N-th repeater.

Each repeater i (1 \leq i \leq N) has a "transmission rate" A_i set as an integer value in percent. If the strength of the signal input to repeater i is C, then the strength of the signal after passing through repeater i becomes \left\lfloor \dfrac{C \times A_i}{100} \right\rfloor. Here, \lfloor x \rfloor denotes the largest integer not exceeding x (the floor function).

The initial strength of the signal emitted from Takahashi's transmitter is M.

Find the strength of the signal after it has passed through all N repeaters in order.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq M \leq 10^{16}
• 1 \leq A_i \leq 100 (1 \leq i \leq N)
• All inputs are integers.

Sample Input 1

3 100
80 50 60

Sample Output 1

24

Sample Input 2

4 7
50 50 50 50

Sample Output 2

0

Sample Input 3

8 12345
99 87 73 100 64 58 91 77

Sample Output 3

2017

Sample Input 4

20 10000000000000000
97 88 76 100 65 54 43 92 81 70 59 48 37 100 99 83 67 52 41 30

Sample Output 4

1884542668173

Sample Input 5

1 1
1

Sample Output 5

0

Problem Statement

Takahashi has been put in charge of organizing the school's dance party. There are N participants, each numbered from 1 to N.

At the dance party, participants form pairs to dance together. However, this school has a unique tradition: each participant i has a positive integer value called "priority" R_i. A person with higher priority (larger value) has the right to choose their partner first.

Aoki is participant number 1, and he is concerned about who his partner will be.

M "pair candidates" have been designated in advance from among the participants. The j-th pair candidate is the pair of participant U_j and participant V_j, meaning that participant U_j and participant V_j are candidates to be paired with each other. Pairs can only be formed from these M candidates.

The pairing rules are as follows:

1. Set all N participants' partners as undetermined.
2. Among the participants whose partner is undetermined, select the one participant with the highest priority R_i. Call this participant x.
3. Among the participants who are pair candidates with participant x and whose partner is undetermined, select the one with the smallest participant number. Call this participant y. Pair participant x with participant y.
4. Repeat steps 2–3 until there are no participants with undetermined partners.

By this rule, a total of N / 2 pairs are formed (N is guaranteed to be even).

Since all priority values R_i are distinct, the participant selected in step 2 is uniquely determined. It is also guaranteed that in step 3, participant x will never have 0 available candidates to choose from (that is, the input is guaranteed to allow every participant to be paired with exactly one partner).

Determine the participant number of Aoki's (participant number 1) partner when the pairs are decided according to this rule.

Constraints

• 2 \leq N \leq 2 \times 10^5
• N is even
• \frac{N}{2} \leq M \leq \min\left(\frac{N(N-1)}{2},\ 2 \times 10^5\right)
• 1 \leq R_i \leq 10^9 (1 \leq i \leq N)
• All R_i are distinct
• 1 \leq U_j < V_j \leq N (1 \leq j \leq M)
• All (U_j, V_j) are distinct
• It is guaranteed that every participant can be paired with exactly one partner
• All input values are integers

Sample Input 1

4 3
10 20 30 40
1 2
1 3
3 4

Sample Output 1

2

Sample Input 2

6 4
100 50 80 70 60 90
1 2
1 3
3 4
5 6

Sample Output 2

2

Sample Input 3

10 7
50 15 25 35 45 55 65 75 85 95
1 2
1 4
2 3
3 4
5 6
7 8
9 10

Sample Output 3

2

Sample Input 4

20 12
50 40 100 90 80 70 60 55 45 35 30 25 20 15 10 5 95 85 75 65
1 2
1 3
2 4
3 4
5 6
7 8
9 10
11 12
13 14
15 16
17 18
19 20

Sample Output 4

3

Sample Input 5

2 1
1 2
1 2

Sample Output 5

2

Problem Statement

Takahashi is analyzing the organizational chart of a company.

The organization consists of N employees, and the organizational chart is represented as a rooted tree. The employees are numbered from 1 to N, and employee 1 is the president (root). Each employee i (2 \leq i \leq N) has a direct supervisor P_i, meaning employee i is a direct subordinate of employee P_i.

Each employee i is assigned a non-negative integer W_i representing their workload. It is guaranteed that for employees who have one or more direct subordinates (managers), W_i = 0. For employees who have no direct subordinates (regular employees, i.e., employees corresponding to leaves of the tree), W_i \geq 0 (including the case W_i = 0).

First, for each employee u, define the team workload S_u of employee u as the sum of the workloads of all employees (including u themselves) in the subtree rooted at employee u. That is, S_u = \displaystyle\sum_{v} W_v (where the sum is taken over all employees v in the subtree rooted at employee u).

Next, define the imbalance of each employee v as follows:

• When employee v has 2 or more direct subordinates: the difference between the maximum and minimum team workloads among the direct subordinates. That is, if the set of direct subordinates of employee v is \{c_1, c_2, \ldots, c_k\} (k \geq 2), then \max(S_{c_1}, \ldots, S_{c_k}) - \min(S_{c_1}, \ldots, S_{c_k}).
• When employee v has 1 or fewer direct subordinates (this includes both managers with exactly 1 direct subordinate and regular employees with no direct subordinates): 0.

Define the imbalance of the entire organization as the maximum imbalance among all employees.

Find the imbalance of the entire organization.

Constraints

• 1 \leq N \leq 2 \times 10^5
• 1 \leq P_i \leq i - 1 (2 \leq i \leq N)
• 0 \leq W_i \leq 10^9 (1 \leq i \leq N)
• When employee i has direct subordinates (is not a leaf), W_i = 0
• All input values are integers

Sample Input 1

3
1 1
0 10 3

Sample Output 1

7

Sample Input 2

7
1 1 2 2 3 3
0 0 0 8 2 9 1

Sample Output 2

8

Sample Input 3

10
1 1 1 2 2 3 4 4 4
0 0 0 0 20 5 12 100 3 1

Sample Output 3

99

Problem Statement

In Takahashi's class, students are to line up in order of height for their physical education class. The teacher wants to understand how spread out the students' heights are, so they decided to calculate the sum of height differences for all pairs of students.

There are N students in the class, and the height of the i-th student is A_i centimeters.

The teacher wants to find the absolute difference in height for every combination of 2 distinct students chosen from the N students, and calculate the total sum.

Specifically, for all pairs (i, j) satisfying 1 \leq i < j \leq N, compute |A_i - A_j| and find their total sum. Even if two students have the same height, as long as they are different individuals, they are counted as one pair.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq A_i \leq 10^8
• All inputs are integers.
• It is guaranteed that the answer is at most 2^{63} - 1 (fits in a 64-bit signed integer).

Sample Input 1

4
150 160 170 180

Sample Output 1

100

Sample Input 2

5
160 160 150 170 150

Sample Output 2

100

Sample Input 3

10
172 165 180 158 165 190 175 168 182 160

Sample Output 3

551

Sample Input 4

20
145 172 168 190 155 160 177 182 149 171 166 158 193 174 169 161 185 152 178 164

Sample Output 4

2975

Sample Input 5

2
1 100000000

Sample Output 5

99999999

Problem Statement

Takahashi is developing an evaluation system for hiking courses. This system calculates a "hiking score" for each of the N courses numbered from 1 to N.

When the number of each course is written in standard decimal notation without leading zeros, let k be the number of digits, and let d_1, d_2, \ldots, d_k be the digits from left (most significant digit) to right. Since the course number is at least 1, we have d_1 \geq 1. Here, d_1, d_2, \ldots, d_k are regarded as the elevations (integers between 0 and 9, inclusive) of the 1st section, 2nd section, …, k-th section of the course, respectively. Each course simulates a mountain trail, and the sequence of digits represents the changes in elevation.

The hiking score is defined as follows.

First, the base score B is defined as the sum of the absolute differences in elevation between all pairs of adjacent sections. That is,

B = \sum_{i=1}^{k-1} |d_i - d_{i+1}|

When the course number has only 1 digit (k = 1), there are no pairs of adjacent sections, so B = 0.

Next, if at least one section among d_1, d_2, \ldots, d_k has elevation 0, the course is considered to have a "rest spot," and the base score is doubled. If no section has elevation 0, the base score remains as is.

That is, defining the multiplier m as

m = \begin{cases} 2 & (\text{if } 0 \text{ is contained among } d_1, d_2, \ldots, d_k) \\ 1 & (\text{otherwise}) \end{cases}

the hiking score of that course is m \times B.

Given an integer N representing the upper limit of course numbers, find the sum of hiking scores of all N courses from course 1 to course N, modulo 10^9 + 7.

Constraints

• 1 \leq N \leq 10^{18}
• N is an integer

Sample Input 1

15

Sample Output 1

12

Sample Input 2

20

Sample Output 2

42

Sample Input 3

1000

Sample Output 3

7652

Sample Input 4

999999999999999999

Sample Output 4

243567135

Sample Input 5

1

Sample Output 5

0