Problem Statement

Takahashi has rolled three dice. They are showing numbers a, b, and c on the top faces.

Find the sum of the numbers on the bottom faces.

Here, each of these dice is a standard cubic die, where the sum of the numbers on opposite faces is 7.

Constrains

• 1 \leq a, b, c \leq 6
• All values in input are integers.

Sample Input 1

1 4 3

Sample Output 1

13

The numbers on the bottom faces are 6, 3, and 4. We have 6 + 3 + 4 = 13, which should be printed.

Sample Input 2

5 6 4

Sample Output 2

6

Problem Statement

You are given a string S consisting of 0, 1, 6, 8, and 9.

Rotate S 180 degrees and print the result. In other words, apply the following operations on S and print the resulting string:

• Reverse S.
• Replace each 0 with a 0, each 1 with a 1, each 6 with a 9, each 8 with an 8, and each 9 with a 6.

Constraints

• 1 \leq |S| \leq 10^5
• S consists of 0, 1, 6, 8, and 9.

Sample Input 1

0601889

Sample Output 1

6881090

Rotating 0601889 180 degrees results in 6881090.

Sample Input 2

86910

Sample Output 2

01698

Sample Input 3

01010

Sample Output 3

01010

S may remain the same.

Problem Statement

Given are three sequences of length N each: A = (A_1, A_2, \dots, A_N), B = (B_1, B_2, \dots, B_N), and C = (C_1, C_2, \dots, C_N), consisting of integers between 1 and N (inclusive).

How many pairs (i, j) of integers between 1 and N (inclusive) satisfy A_i = B_{C_j}?

Constraints

• 1 \leq N \leq 10^5
• 1 \leq A_i, B_i, C_i \leq N
• All values in input are integers.

Sample Input 1

3
1 2 2
3 1 2
2 3 2

Sample Output 1

4

Four pairs satisfy the condition: (1, 1), (1, 3), (2, 2), (3, 2).

Sample Input 2

4
1 1 1 1
1 1 1 1
1 2 3 4

Sample Output 2

16

All the pairs satisfy the condition.

Sample Input 3

3
2 3 3
1 3 3
1 1 1

Sample Output 3

0

No pair satisfies the condition.

Problem Statement

Among the strings of length A + B containing A occurrences of a and B occurrences of b, find the string that comes K-th in the lexicographical order.

Constraints

• 1 \leq A, B \leq 30
• 1 \leq K \leq S, where S is the number of strings of length A + B containing A occurrences of a and B occurrences of b.
• All values in input are integers.

Sample Input 1

2 2 4

Sample Output 1

baab

Here are the strings containing two as and two bs in the lexicographical order: aabb, abab, abba, baab, baba, and bbaa. The fourth string, baab, should be printed.

Sample Input 2

30 30 118264581564861424

Sample Output 2

bbbbbbbbbbbbbbbbbbbbbbbbbbbbbbaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

K may not fit into a 32-bit integer type.

Problem Statement

We have a rooted tree with N vertices, numbered 1, 2, \dots, N.

Vertex 1 is the root, and the parent of Vertex i \, (2 \leq i \leq N) is Vertex P_i.

You are given Q queries. In the i-th query (1 \leq i \leq Q), given integers U_i and D_i, find the number of vertices u that satisfy all of the following conditions:

• Vertex U_i is in the shortest path from u to the root (including the endpoints).
• There are exactly D_i edges in the shortest path from u to the root.

Constraints

• 2 \leq N \leq 2 \times 10^5
• 1 \leq P_i < i
• 1 \leq Q \leq 2 \times 10^5
• 1 \leq U_i \leq N
• 0 \leq D_i \leq N - 1
• All values in input are integers.

Sample Input 1

7
1 1 2 2 4 2
4
1 2
7 2
4 1
5 5

Sample Output 1

3
1
0
0

In the 1-st query, Vertices 4, 5, and 7 satisfy the conditions. In the 2-nd query, only Vertices 7 satisfies the conditions. In the 3-rd and 4-th queries, no vertice satisfies the conditions.

Problem Statement

We have N points P_1, P_2, \dots, P_N on a plane. The coordinates of P_i is (X_i, Y_i). We know that no three points lie on the same line.

For a subset S of \{ P_1, P_2, \dots, P_N \} with at least three elements, let us define the convex hull of S as follows:

• The convex hull is the convex polygon with the minimum area such that every point of S is within or on the circumference of that polygon.

Find the number, modulo (10^9 + 7), of subsets S such that the area of the convex hull is an integer.

Constraints

• 3 \leq N \leq 80
• 0 \leq |X_i|, |Y_i| \leq 10^4
• No three points lie on the same line.
• All values in input are integers.

Sample Input 1

4
0 0
1 2
0 1
1 0

Sample Output 1

2

\{ P_1, P_2, P_4 \} and \{ P_2, P_3, P_4 \} satisfy the condition.

Sample Input 2

23
-5255 7890
5823 7526
5485 -113
7302 5708
9149 2722
4904 -3918
8566 -3267
-3759 2474
-7286 -1043
-1230 1780
3377 -7044
-2596 -6003
5813 -9452
-9889 -7423
2377 1811
5351 4551
-1354 -9611
4244 1958
8864 -9889
507 -8923
6948 -5016
-6139 2769
4103 9241

Sample Output 2

4060436