Problem Statement

Snuke built an online judge to hold a programming contest.

When a program is submitted to the judge, the judge returns a verdict, which is a two-character string that appears in the string S as a contiguous substring. (The judge can return any two-character substring of S.)

Determine whether the judge can return the string AC as the verdict to a program.

Constraints

• 2 \leq |S| \leq 5
• S consists of uppercase English letters.

Sample Input 1

BACD

Sample Output 1

Yes

The string AC appears in BACD as a contiguous substring (the second and third characters).

Sample Input 2

ABCD

Sample Output 2

No

Although the string ABCD contains both A and C (the first and third characters), the string AC does not appear in ABCD as a contiguous substring.

Sample Input 3

CABD

Sample Output 3

No

Sample Input 4

ACACA

Sample Output 4

Yes

Sample Input 5

XX

Sample Output 5

No

Problem Statement

We will say that two integer sequences of length N, x_1, x_2, ..., x_N and y_1, y_2, ..., y_N, are similar when |x_i - y_i| \leq 1 holds for all i (1 \leq i \leq N).

In particular, any integer sequence is similar to itself.

You are given an integer N and an integer sequence of length N, A_1, A_2, ..., A_N.

How many integer sequences b_1, b_2, ..., b_N are there such that b_1, b_2, ..., b_N is similar to A and the product of all elements, b_1 b_2 ... b_N, is even?

Constraints

• 1 \leq N \leq 10
• 1 \leq A_i \leq 100

Sample Input 1

2
2 3

Sample Output 1

7

There are seven integer sequences that satisfy the condition:

• 1, 2
• 1, 4
• 2, 2
• 2, 3
• 2, 4
• 3, 2
• 3, 4

Sample Input 2

3
3 3 3

Sample Output 2

26

Sample Input 3

1
100

Sample Output 3

1

Sample Input 4

10
90 52 56 71 44 8 13 30 57 84

Sample Output 4

58921

Problem Statement

We have a string s consisting of lowercase English letters. Snuke can perform the following operation repeatedly:

• Insert a letter x to any position in s of his choice, including the beginning and end of s.

Snuke's objective is to turn s into a palindrome. Determine whether the objective is achievable. If it is achievable, find the minimum number of operations required.

Notes

A palindrome is a string that reads the same forward and backward. For example, a, aa, abba and abcba are palindromes, while ab, abab and abcda are not.

Constraints

• 1 \leq |s| \leq 10^5
• s consists of lowercase English letters.

Sample Input 1

xabxa

Sample Output 1

2

One solution is as follows (newly inserted x are shown in bold):

xabxa → xaxbxa → xaxbxax

Sample Input 2

ab

Sample Output 2

-1

No sequence of operations can turn s into a palindrome.

Sample Input 3

a

Sample Output 3

0

s is a palindrome already at the beginning.

Sample Input 4

oxxx

Sample Output 4

3

One solution is as follows:

oxxx → xoxxx → xxoxxx → xxxoxxx

Problem Statement

We have a string s consisting of lowercase English letters. Snuke is partitioning s into some number of non-empty substrings. Let the subtrings obtained be s_1, s_2, ..., s_N from left to right. (Here, s = s_1 + s_2 + ... + s_N holds.) Snuke wants to satisfy the following condition:

• For each i (1 \leq i \leq N), it is possible to permute the characters in s_i and obtain a palindrome.

Find the minimum possible value of N when the partition satisfies the condition.

Constraints

• 1 \leq |s| \leq 2 \times 10^5
• s consists of lowercase English letters.

Sample Input 1

aabxyyzz

Sample Output 1

2

The solution is to partition s as aabxyyzz = aab + xyyzz. Here, aab can be permuted to form a palindrome aba, and xyyzz can be permuted to form a palindrome zyxyz.

Sample Input 2

byebye

Sample Output 2

1

byebye can be permuted to form a palindrome byeeyb.

Sample Input 3

abcdefghijklmnopqrstuvwxyz

Sample Output 3

26

Sample Input 4

abcabcxabcx

Sample Output 4

3

The solution is to partition s as abcabcxabcx = a + b + cabcxabcx.

Problem Statement

We constructed a rectangular parallelepiped of dimensions A \times B \times C built of ABC cubic blocks of side 1. Then, we placed the parallelepiped in xyz-space as follows:

• For every triple i, j, k (0 \leq i < A, 0 \leq j < B, 0 \leq k < C), there exists a block that has a diagonal connecting the points (i, j, k) and (i + 1, j + 1, k + 1). All sides of the block are parallel to a coordinate axis.

For each triple i, j, k, we will call the above block as block (i, j, k).

For two blocks (i_1, j_1, k_1) and (i_2, j_2, k_2), we will define the distance between them as max(|i_1 - i_2|, |j_1 - j_2|, |k_1 - k_2|).

We have passed a wire with a negligible thickness through a segment connecting the points (0, 0, 0) and (A, B, C). How many blocks (x,y,z) satisfy the following condition? Find the count modulo 10^9 + 7.

• There exists a block (x', y', z') such that the wire passes inside the block (x', y', z') (not just boundary) and the distance between the blocks (x, y, z) and (x', y', z') is at most D.

Constraints

• 1 \leq A < B < C \leq 10^{9}
• Any two of the three integers A, B and C are coprime.
• 0 \leq D \leq 50,000

Sample Input 1

3 4 5 1

Sample Output 1

54

The figure below shows the parallelepiped, sliced into five layers by planes parallel to xy-plane. Here, the layer in the region i - 1 \leq z \leq i is called layer i.

The blocks painted black are penetrated by the wire, and satisfy the condition. The other blocks that satisfy the condition are painted yellow.

There are 54 blocks that are painted black or yellow.

Sample Input 2

1 2 3 0

Sample Output 2

4

There are four blocks that are penetrated by the wire, and only these blocks satisfy the condition.

Sample Input 3

3 5 7 100

Sample Output 3

105

All blocks satisfy the condition.

Sample Input 4

3 123456781 1000000000 100

Sample Output 4

444124403

Sample Input 5

1234 12345 1234567 5

Sample Output 5

150673016

Sample Input 6

999999997 999999999 1000000000 50000

Sample Output 6

8402143

Problem Statement

Three men, A, B and C, are eating sushi together. Initially, there are N pieces of sushi, numbered 1 through N. Here, N is a multiple of 3.

Each of the three has likes and dislikes in sushi. A's preference is represented by (a_1,\ ...,\ a_N), a permutation of integers from 1 to N. For each i (1 \leq i \leq N), A's i-th favorite sushi is Sushi a_i. Similarly, B's and C's preferences are represented by (b_1,\ ...,\ b_N) and (c_1,\ ...,\ c_N), permutations of integers from 1 to N.

The three repeats the following action until all pieces of sushi are consumed or a fight brakes out (described later):

• Each of the three A, B and C finds his most favorite piece of sushi among the remaining pieces. Let these pieces be Sushi x, y and z, respectively. If x, y and z are all different, A, B and C eats Sushi x, y and z, respectively. Otherwise, a fight brakes out.

You are given A's and B's preferences, (a_1,\ ...,\ a_N) and (b_1,\ ...,\ b_N). How many preferences of C, (c_1,\ ...,\ c_N), leads to all the pieces of sushi being consumed without a fight? Find the count modulo 10^9+7.

Constraints

• 3 \leq N \leq 399
• N is a multiple of 3.
• (a_1,\ ...,\ a_N) and (b_1,\ ...,\ b_N) are permutations of integers from 1 to N.

Sample Input 1

3
1 2 3
2 3 1

Sample Output 1

2

The answer is two, (c_1,\ c_2,\ c_3) = (3,\ 1,\ 2),\ (3,\ 2,\ 1). In both cases, A, B and C will eat Sushi 1, 2 and 3, respectively, and there will be no more sushi.

Sample Input 2

3
1 2 3
1 2 3

Sample Output 2

0

Regardless of what permutation (c_1,\ c_2,\ c_3) is, A and B will try to eat Sushi 1, resulting in a fight.

Sample Input 3

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

Sample Output 3

80

For example, if (c_1,\ c_2,\ c_3,\ c_4,\ c_5,\ c_6) = (5,\ 1,\ 2,\ 6,\ 3,\ 4), A, B and C will first eat Sushi 1, 2 and 5, respectively, then they will eat Sushi 3, 4 and 6, respectively, and there will be no more sushi.

Sample Input 4

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

Sample Output 4

160

Sample Input 5

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

Sample Output 5

33600