Problem Statement

You are given a string S of length N. Among its subsequences, count the ones such that all characters are different, modulo 10^9+7. Two subsequences are considered different if their characters come from different positions in the string, even if they are the same as strings.

Here, a subsequence of a string is a concatenation of one or more characters from the string without changing the order.

Constraints

• 1 \leq N \leq 100000
• S consists of lowercase English letters.
• |S|=N

Sample Input 1

4
abcd

Sample Output 1

15

Since all characters in S itself are different, all its subsequences satisfy the condition.

Sample Input 2

3
baa

Sample Output 2

5

The answer is five: b, two occurrences of a, two occurrences of ba. Note that we do not count baa, since it contains two as.

Sample Input 3

5
abcab

Sample Output 3

17

Problem Statement

There are N stones arranged in a row. The i-th stone from the left is painted in the color C_i.

Snuke will perform the following operation zero or more times:

• Choose two stones painted in the same color. Repaint all the stones between them, with the color of the chosen stones.

Find the number of possible final sequences of colors of the stones, modulo 10^9+7.

Constraints

• 1 \leq N \leq 2\times 10^5
• 1 \leq C_i \leq 2\times 10^5(1\leq i\leq N)
• All values in input are integers.

Sample Input 1

5
1
2
1
2
2

Sample Output 1

3

We can make three sequences of colors of stones, as follows:

• (1,2,1,2,2), by doing nothing.
• (1,1,1,2,2), by choosing the first and third stones to perform the operation.
• (1,2,2,2,2), by choosing the second and fourth stones to perform the operation.

Sample Input 2

6
4
2
5
4
2
4

Sample Output 2

5

Sample Input 3

7
1
3
1
2
3
3
2

Sample Output 3

5

Problem Statement

You are given integers N,\ A and B. Determine if there exists a permutation (P_0,\ P_1,\ ...\ P_{2^N-1}) of (0,\ 1,\ ...\ 2^N-1) that satisfies all of the following conditions, and create one such permutation if it exists.

• P_0=A
• P_{2^N-1}=B
• For all 0 \leq i < 2^N-1, the binary representations of P_i and P_{i+1} differ by exactly one bit.

Constraints

• 1 \leq N \leq 17
• 0 \leq A \leq 2^N-1
• 0 \leq B \leq 2^N-1
• A \neq B
• All values in input are integers.

Sample Input 1

2 1 3

Sample Output 1

YES
1 0 2 3

The binary representation of P=(1,0,2,3) is (01,00,10,11), where any two adjacent elements differ by exactly one bit.

Sample Input 2

3 2 1

Sample Output 2

NO

Problem Statement

For two permutations p and q of the integers from 1 through N, let f(p,q) be the permutation that satisfies the following:

• The p_i-th element (1 \leq i \leq N) in f(p,q) is q_i. Here, p_i and q_i respectively denote the i-th element in p and q.

You are given two permutations p and q of the integers from 1 through N. We will now define a sequence {a_n} of permutations of the integers from 1 through N, as follows:

• a_1=p, a_2=q
• a_{n+2}=f(a_n,a_{n+1}) ( n \geq 1 )

Given a positive integer K, find a_K.

Constraints

• 1 \leq N \leq 10^5
• 1 \leq K \leq 10^9
• p and q are permutations of the integers from 1 through N.

Sample Input 1

3 3
1 2 3
3 2 1

Sample Output 1

3 2 1

Since a_3=f(p,q), we just need to find f(p,q). We have p_i=i here, so f(p,q)=q.

Sample Input 2

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

Sample Output 2

4 3 2 1 5

Sample Input 3

10 1000000000
7 10 6 5 4 2 9 1 3 8
4 1 9 2 3 7 8 10 6 5

Sample Output 3

7 9 4 8 2 5 1 6 10 3

Problem Statement

A museum exhibits N jewels, Jewel 1, 2, ..., N. The coordinates of Jewel i are (x_i, y_i) (the museum can be regarded as a two-dimensional plane), and the value of that jewel is v_i.

Snuke the thief will steal some of these jewels.

There are M conditions, Condition 1, 2, ..., M, that must be met when stealing jewels, or he will be caught by the detective. Each condition has one of the following four forms:

• (t_i =L, a_i, b_i) : Snuke can only steal at most b_i jewels whose x coordinates are a_i or smaller.
• (t_i =R, a_i, b_i) : Snuke can only steal at most b_i jewels whose x coordinates are a_i or larger.
• (t_i =D, a_i, b_i) : Snuke can only steal at most b_i jewels whose y coordinates are a_i or smaller.
• (t_i =U, a_i, b_i) : Snuke can only steal at most b_i jewels whose y coordinates are a_i or larger.

Find the maximum sum of values of jewels that Snuke the thief can steal.

Constraints

• 1 \leq N \leq 80
• 1 \leq x_i, y_i \leq 100
• 1 \leq v_i \leq 10^{15}
• 1 \leq M \leq 320
• t_i is L, R, U or D.
• 1 \leq a_i \leq 100
• 0 \leq b_i \leq N - 1
• (x_i, y_i) are pairwise distinct.
• (t_i, a_i) are pairwise distinct.
• (t_i, b_i) are pairwise distinct.

Sample Input 1

7
1 3 6
1 5 9
3 1 8
4 3 8
6 2 9
5 4 11
5 7 10
4
L 3 1
R 2 3
D 5 3
U 4 2

Sample Output 1

36

Stealing Jewel 1, 5, 6 and 7 results in the total value of 36.

Sample Input 2

3
1 2 3
4 5 6
7 8 9
1
L 100 0

Sample Output 2

0

Sample Input 3

4
1 1 10
1 2 11
2 1 12
2 2 13
3
L 8 3
L 9 2
L 10 1

Sample Output 3

13

Sample Input 4

10
66 47 71040136000
65 77 74799603000
80 53 91192869000
24 34 24931901000
91 78 49867703000
68 71 46108236000
46 73 74799603000
56 63 93122668000
32 51 71030136000
51 26 70912345000
21
L 51 1
L 7 0
U 47 4
R 92 0
R 91 1
D 53 2
R 65 3
D 13 0
U 63 3
L 68 3
D 47 1
L 91 5
R 32 4
L 66 2
L 80 4
D 77 4
U 73 1
D 78 5
U 26 5
R 80 2
R 24 5

Sample Output 4

305223377000

Problem Statement

You are given a connected graph with N vertices and M edges. The vertices are numbered 1 to N. The i-th edge is an undirected edge of length C_i connecting Vertex A_i and Vertex B_i.

Additionally, an odd number MOD is given.

You will be given Q queries, which should be processed. The queries take the following form:

• Given in the i-th query are S_i, T_i and R_i. Print YES if there exists a path from Vertex S_i to Vertex T_i whose length is R_i modulo MOD, and print NO otherwise. A path may traverse the same edge multiple times, or go back using the edge it just used.

Here, in this problem, the length of a path is NOT the sum of the lengths of its edges themselves, but the length of the first edge used in the path gets multiplied by 1, the second edge gets multiplied by 2, the third edge gets multiplied by 4, and so on. (More formally, let L_1,...,L_k be the lengths of the edges used, in this order. The length of that path is the sum of L_i \times 2^{i-1}.)

Constraints

• 1 \leq N,M,Q \leq 50000
• 3 \leq MOD \leq 10^{6}
• MOD is odd.
• 1 \leq A_i,B_i\leq N
• 0 \leq C_i \leq MOD-1
• 1 \leq S_i,T_i \leq N
• 0 \leq R_i \leq MOD-1
• The given graph is connected. (It may contain self-loops or multiple edges.)

Sample Input 1

3 2 2 2019
1 2 1
2 3 2
1 3 5
1 3 4

Sample Output 1

YES
NO

The answer to each query is as follows:

• The first query: If we take the path 1,2,3, its length is 1 \times 2^0 + 2 \times 2^1 = 5, so there exists a path whose length is 5 modulo 2019. The answer is YES.
• The second query: No matter what path we take from Vertex 1 to Vertex 3, its length will never be 4 modulo 2019. The answer is NO.

Sample Input 2

6 6 3 2019
1 2 4
2 3 4
3 4 4
4 5 4
5 6 4
6 1 4
2 6 1110
3 1 1111
4 5 1112

Sample Output 2

YES
NO
NO

Sample Input 3

1 2 3 25
1 1 1
1 1 2
1 1 13
1 1 6
1 1 14

Sample Output 3

YES
YES
YES

Sample Input 4

10 15 10 15
1 2 1
2 3 6
3 4 6
2 5 1
5 6 1
4 7 6
1 8 11
2 9 6
5 10 11
9 10 11
3 6 1
2 5 1
2 7 11
9 10 11
5 6 11
1 3 5
9 8 3
7 7 7
7 10 13
4 1 10
9 3 12
10 10 14
9 2 1
6 6 5
8 8 4

Sample Output 4

YES
NO
NO
NO
NO
NO
NO
YES
YES
NO