Problem Statement

In this problem, we use the 24-hour clock.

Takahashi gets up exactly at the time H_1 : M_1 and goes to bed exactly at the time H_2 : M_2. (See Sample Inputs below for clarity.) He has decided to study for K consecutive minutes while he is up. What is the length of the period in which he can start studying?

Constraints

• 0 \le H_1, H_2 \le 23
• 0 \le M_1, M_2 \le 59
• The time H_1 : M_1 comes before the time H_2 : M_2.
• K \ge 1
• Takahashi is up for at least K minutes.
• All values in input are integers (without leading zeros).

Sample Input 1

10 0 15 0 30

Sample Output 1

270

Takahashi gets up at exactly ten in the morning and goes to bed at exactly three in the afternoon. It takes 30 minutes to do the study, so he can start it in the period between ten o'clock and half-past two. The length of this period is 270 minutes, so we should print 270.

Sample Input 2

10 0 12 0 120

Sample Output 2

0

Takahashi gets up at exactly ten in the morning and goes to bed at exactly noon. It takes 120 minutes to do the study, so he has to start it at exactly ten o'clock. Thus, we should print 0.

Problem Statement

For a string S consisting of the uppercase English letters P and D, let the doctoral and postdoctoral quotient of S be the total number of occurrences of D and PD in S as contiguous substrings. For example, if S = PPDDP, it contains two occurrences of D and one occurrence of PD as contiguous substrings, so the doctoral and postdoctoral quotient of S is 3.

We have a string T consisting of P, D, and ?.

Among the strings that can be obtained by replacing each ? in T with P or D, find one with the maximum possible doctoral and postdoctoral quotient.

Constraints

• 1 \leq |T| \leq 2 \times 10^5
• T consists of P, D, and ?.

Sample Input 1

PD?D??P

Sample Output 1

PDPDPDP

This string contains three occurrences of D and three occurrences of PD as contiguous substrings, so its doctoral and postdoctoral quotient is 6, which is the maximum doctoral and postdoctoral quotient of a string obtained by replacing each ? in T with P or D.

Sample Input 2

P?P?

Sample Output 2

PDPD

Problem Statement

Given is an integer sequence of length N+1: A_0, A_1, A_2, \ldots, A_N. Is there a binary tree of depth N such that, for each d = 0, 1, \ldots, N, there are exactly A_d leaves at depth d? If such a tree exists, print the maximum possible number of vertices in such a tree; otherwise, print -1.

Notes

• A binary tree is a rooted tree such that each vertex has at most two direct children.
• A leaf in a binary tree is a vertex with zero children.
• The depth of a vertex v in a binary tree is the distance from the tree's root to v. (The root has the depth of 0.)
• The depth of a binary tree is the maximum depth of a vertex in the tree.

Constraints

• 0 \leq N \leq 10^5
• 0 \leq A_i \leq 10^{8} (0 \leq i \leq N)
• A_N \geq 1
• All values in input are integers.

Sample Input 1

3
0 1 1 2

Sample Output 1

7

Below is the tree with the maximum possible number of vertices. It has seven vertices, so we should print 7.

Sample Input 2

4
0 0 1 0 2

Sample Output 2

10

Sample Input 3

2
0 3 1

Sample Output 3

-1

Sample Input 4

1
1 1

Sample Output 4

-1

Sample Input 5

10
0 0 1 1 2 3 5 8 13 21 34

Sample Output 5

264

Problem Statement

There are N towns numbered 1, 2, \cdots, N.

Some roads are planned to be built so that each of them connects two distinct towns bidirectionally. Currently, there are no roads connecting towns.

In the planning of construction, each town chooses one town different from itself and requests the following: roads are built so that the chosen town is reachable from itself using one or more roads.

These requests from the towns are represented by an array P_1, P_2, \cdots, P_N. If P_i = -1, it means that Town i has not chosen the request; if 1 \leq P_i \leq N, it means that Town i has chosen Town P_i.

Let K be the number of towns i such that P_i = -1. There are (N-1)^K ways in which the towns can make the requests. For each way to make requests, find the minimum number of roads needed to meet all the requests, and print the sum of those (N-1)^K numbers, modulo (10^9+7).

Constraints

• 2 \leq N \leq 5000
• P_i = -1 or 1 \leq P_i \leq N.
• P_i \neq i
• All values in input are integers.

Sample Input 1

4
2 1 -1 3

Sample Output 1

8

There are three ways to make requests, as follows:

• Choose P_1 = 2, P_2 = 1, P_3 = 1, P_4 = 3. In this case, at least three roads - for example, (1,2),(1,3),(3,4) - are needed to meet the requests.
• Choose P_1 = 2, P_2 = 1, P_3 = 2, P_4 = 3. In this case, at least three roads - for example, (1,2),(1,3),(3,4) - are needed to meet the requests.
• Choose P_1 = 2, P_2 = 1, P_3 = 4, P_4 = 3. In this case, at least two roads - for example, (1,2),(3,4) - are needed to meet the requests.

Note that it is not mandatory to connect Town i and Town P_i directly.

The sum of the above numbers is 8.

Sample Input 2

2
2 1

Sample Output 2

1

There may be just one fixed way to make requests.

Sample Input 3

10
2 6 9 -1 6 9 -1 -1 -1 -1

Sample Output 3

527841

Problem Statement

Takahashi has an empty string S and a variable x whose initial value is 0.

Also, we have a string T consisting of 0 and 1.

Now, Takahashi will do the operation with the following two steps |T| times.

• Insert a 0 or a 1 at any position of S of his choice.
• Then, increment x by the sum of the digits in the odd positions (first, third, fifth, ...) of S. For example, if S is 01101, the digits in the odd positions are 0, 1, 1 from left to right, so x is incremented by 2.

Print the maximum possible final value of x in a sequence of operations such that S equals T in the end.

Constraints

• 1 \leq |T| \leq 2 \times 10^5
• T consists of 0 and 1.

Sample Input 1

1101

Sample Output 1

5

Below is one sequence of operations that maximizes the final value of x to 5.

• Insert a 1 at the beginning of S. S becomes 1, and x is incremented by 1.
• Insert a 0 to the immediate right of the first character of S. S becomes 10, and x is incremented by 1.
• Insert a 1 to the immediate right of the second character of S. S becomes 101, and x is incremented by 2.
• Insert a 1 at the beginning of S. S becomes 1101, and x is incremented by 1.

Sample Input 2

0111101101

Sample Output 2

26

Problem Statement

Takahashi and Snuke came up with a game that uses a number sequence, as follows:

• Prepare a sequence of length M consisting of integers between 0 and 2^N-1 (inclusive): a = a_1, a_2, \ldots, a_M.

• Snuke first does the operation below as many times as he likes:

  • Choose a positive integer d, and for each i (1 \leq i \leq M), in binary, set the d-th least significant bit of a_i to 0. (Here the least significant bit is considered the 1-st least significant bit.)

• After Snuke finishes doing operations, Takahashi tries to sort a in ascending order by doing the operation below some number of times. Here a is said to be in ascending order when a_i \leq a_{i + 1} for all i (1 \leq i \leq M - 1).

  • Choose two adjacent elements of a: a_i and a_{i + 1}. If, in binary, these numbers differ in exactly one bit, swap a_i and a_{i + 1}.

There are 2^{NM} different sequences of length M consisting of integers between 0 and 2^N-1 that can be used in the game.

How many among them have the following property: if used in the game, there is always a way for Takahashi to sort the sequence in ascending order regardless of Snuke's operations? Find the count modulo (10^9 + 7).

Constraints

• All values in input are integers.
• 1 \leq N \leq 5000
• 2 \leq M \leq 5000

Sample Input 1

2 5

Sample Output 1

352

Consider the case a = 1, 3, 1, 3, 1 for example.

• When the least significant bit of each element of a is set to 0, a = 0, 2, 0, 2, 0;
• When the second least significant bit of each element of a is set to 0, a = 1, 1, 1, 1, 1;
• When the least two significant bits of each element of a are set to 0, a = 0, 0, 0, 0, 0.

In all of the cases above and the case when Snuke does no operation to change a, we can sort the sequence by repeatedly swapping adjacent elements that differ in exactly one bit. Thus, this sequence has the property: if used in the game, there is always a way for Takahashi to sort the sequence in ascending order regardless of Snuke's operations.

Sample Input 2

2020 530

Sample Output 2

823277409