Problem Statement

You are given a sequence of positive integers of length N, a = (a_1, a_2, ..., a_N). Your objective is to remove some of the elements in a so that a will be a good sequence.

Here, an sequence b is a good sequence when the following condition holds true:

• For each element x in b, the value x occurs exactly x times in b.

For example, (3, 3, 3), (4, 2, 4, 1, 4, 2, 4) and () (an empty sequence) are good sequences, while (3, 3, 3, 3) and (2, 4, 1, 4, 2) are not.

Find the minimum number of elements that needs to be removed so that a will be a good sequence.

Constraints

• 1 \leq N \leq 10^5
• a_i is an integer.
• 1 \leq a_i \leq 10^9

Sample Input 1

4
3 3 3 3

Sample Output 1

1

We can, for example, remove one occurrence of 3. Then, (3, 3, 3) is a good sequence.

Sample Input 2

5
2 4 1 4 2

Sample Output 2

2

We can, for example, remove two occurrences of 4. Then, (2, 1, 2) is a good sequence.

Sample Input 3

6
1 2 2 3 3 3

Sample Output 3

0

Sample Input 4

1
1000000000

Sample Output 4

1

Remove one occurrence of 10^9. Then, () is a good sequence.

Sample Input 5

8
2 7 1 8 2 8 1 8

Sample Output 5

5

Problem Statement

A robot is put at the origin in a two-dimensional plane. Initially, the robot is facing in the positive x-axis direction.

This robot will be given an instruction sequence s. s consists of the following two kinds of letters, and will be executed in order from front to back.

• F : Move in the current direction by distance 1.
• T : Turn 90 degrees, either clockwise or counterclockwise.

The objective of the robot is to be at coordinates (x, y) after all the instructions are executed. Determine whether this objective is achievable.

Constraints

• s consists of F and T.
• 1 \leq |s| \leq 8 000
• x and y are integers.
• |x|, |y| \leq |s|

Sample Input 1

FTFFTFFF
4 2

Sample Output 1

Yes

The objective can be achieved by, for example, turning counterclockwise in the first T and turning clockwise in the second T.

Sample Input 2

FTFFTFFF
-2 -2

Sample Output 2

Yes

The objective can be achieved by, for example, turning clockwise in the first T and turning clockwise in the second T.

Sample Input 3

FF
1 0

Sample Output 3

No

Sample Input 4

TF
1 0

Sample Output 4

No

Sample Input 5

FFTTFF
0 0

Sample Output 5

Yes

The objective can be achieved by, for example, turning counterclockwise in the first T and turning counterclockwise in the second T.

Sample Input 6

TTTT
1 0

Sample Output 6

No

Problem Statement

For strings s and t, we will say that s and t are prefix-free when neither is a prefix of the other.

Let L be a positive integer. A set of strings S is a good string set when the following conditions hold true:

• Each string in S has a length between 1 and L (inclusive) and consists of the characters 0 and 1.
• Any two distinct strings in S are prefix-free.

We have a good string set S = \{ s_1, s_2, ..., s_N \}. Alice and Bob will play a game against each other. They will alternately perform the following operation, starting from Alice:

• Add a new string to S. After addition, S must still be a good string set.

The first player who becomes unable to perform the operation loses the game. Determine the winner of the game when both players play optimally.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq L \leq 10^{18}
• s_1, s_2, ..., s_N are all distinct.
• { s_1, s_2, ..., s_N } is a good string set.
• |s_1| + |s_2| + ... + |s_N| \leq 10^5

Sample Input 1

2 2
00
01

Sample Output 1

Alice

If Alice adds 1, Bob will be unable to add a new string.

Sample Input 2

2 2
00
11

Sample Output 2

Bob

There are two strings that Alice can add on the first turn: 01 and 10. In case she adds 01, if Bob add 10, she will be unable to add a new string. Also, in case she adds 10, if Bob add 01, she will be unable to add a new string.

Sample Input 3

3 3
0
10
110

Sample Output 3

Alice

If Alice adds 111, Bob will be unable to add a new string.

Sample Input 4

2 1
0
1

Sample Output 4

Bob

Alice is unable to add a new string on the first turn.

Sample Input 5

1 2
11

Sample Output 5

Alice

Sample Input 6

2 3
101
11

Sample Output 6

Bob

Problem Statement

There is a tree with N vertices. The vertices are numbered 1 through N. The i-th edge (1 \leq i \leq N - 1) connects Vertex x_i and y_i. For vertices v and w (1 \leq v, w \leq N), we will define the distance between v and w d(v, w) as "the number of edges contained in the path v-w".

A squirrel lives in each vertex of the tree. They are planning to move, as follows. First, they will freely choose a permutation of (1, 2, ..., N), p = (p_1, p_2, ..., p_N). Then, for each 1 \leq i \leq N, the squirrel that lived in Vertex i will move to Vertex p_i.

Since they like long travels, they have decided to maximize the total distance they traveled during the process. That is, they will choose p so that d(1, p_1) + d(2, p_2) + ... + d(N, p_N) will be maximized. How many such ways are there to choose p, modulo 10^9 + 7?

Constraints

• 2 \leq N \leq 5,000
• 1 \leq x_i, y_i \leq N
• The input graph is a tree.

Sample Input 1

3
1 2
2 3

Sample Output 1

3

The maximum possible distance traveled by squirrels is 4. There are three choices of p that achieve it, as follows:

• (2, 3, 1)
• (3, 1, 2)
• (3, 2, 1)

Sample Input 2

4
1 2
1 3
1 4

Sample Output 2

11

The maximum possible distance traveled by squirrels is 6. For example, p = (2, 1, 4, 3) achieves it.

Sample Input 3

6
1 2
1 3
1 4
2 5
2 6

Sample Output 3

36

Sample Input 4

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

Sample Output 4

396