Problem Statement

You are given an integer N. Compute and output the value of 2^N-2N.

Constraints

• N is an integer between 1 and 11, inclusive.

Sample Input 1

1

Sample Output 1

0

The value of N given in this input is 1, so output the value of 2^1 - 2 \times 1, which is 0.

Sample Input 2

2

Sample Output 2

0

The value of N given in this input is 2, so output the value of 2^2 - 2 \times 2, which is 0.

Sample Input 3

11

Sample Output 3

2026

The value of N given in this input is 11, so output the value of 2^{11} - 2 \times 11, which is 2026.

Problem Statement

You are given a positive integer N. Determine whether N is a happy number.

A happy number is a non-negative integer that becomes 1 after repeating the following operation a finite number of times:

• Replace it with the integer obtained by taking the sum of the squares of the digits in its decimal representation.
  • For example, performing this operation once on 2026 replaces it with 2^2+0^2+2^2+6^2 = 4+0+4+36 = 44.

For examples of happy numbers, refer to the explanations of sample inputs and outputs.

Constraints

• N is an integer between 1 and 2026, inclusive.

Sample Input 1

2026

Sample Output 1

Yes

2026 is a happy number.

• The digits of 2026 in decimal representation are 2,0,2,6, and taking the sum of their squares gives 2^2+0^2+2^2+6^2 = 4+0+4+36 = 44.
• The digits of 44 in decimal representation are 4,4, and taking the sum of their squares gives 4^2+4^2 = 16+16 = 32.
• The digits of 32 in decimal representation are 3,2, and taking the sum of their squares gives 3^2+2^2 = 9+4 = 13.
• The digits of 13 in decimal representation are 1,3, and taking the sum of their squares gives 1^2+3^2 = 1+9 = 10.
• The digits of 10 in decimal representation are 1,0, and taking the sum of their squares gives 1^2+0^2 = 1+0 = 1.

2026 is a happy number because it became 1 after repeating the operation of replacing itself with the integer obtained by taking the sum of the squares of the digits in its decimal representation five times.

Sample Input 2

439

Sample Output 2

No

439 is not a happy number.

Repeating the operation makes it 439 \rightarrow 106 \rightarrow 37 \rightarrow 58 \rightarrow 89 \rightarrow 145 \rightarrow 42 \rightarrow 20 \rightarrow 4 \rightarrow 16 \rightarrow 37 \rightarrow \dotsb, and it can be proved that no matter how many times the operation is repeated from here, it will not become 1.

Sample Input 3

440

Sample Output 3

Yes

440 is a happy number.

Problem Statement

A positive integer n is called a good integer when it satisfies the following condition:

• There exists exactly one pair of integers (x,y) that satisfies 0 \lt x \lt y and x^2+y^2=n.

For example, when n=2026, it can be verified that (x,y)=(1,45) is the only pair of integers that satisfies 0 \lt x \lt y and x^2+y^2=n. Thus, 2026 is a good integer.

You are given a positive integer N. Enumerate all good integers not exceeding N.

Constraints

• 1 \leq N \leq 10^7
• N is an integer.

Sample Input 1

10

Sample Output 1

2
5 10

(x,y)=(1,2) is the only pair of integers that satisfies 0 \lt x \lt y and x^2+y^2=5, so 5 is a good integer.
(x,y)=(1,3) is the only pair of integers that satisfies 0 \lt x \lt y and x^2+y^2=10, so 10 is a good integer.
These are the only two good integers not exceeding N.

Sample Input 2

1

Sample Output 2

0

Sample Input 3

50

Sample Output 3

14
5 10 13 17 20 25 26 29 34 37 40 41 45 50

Problem Statement

You are given an integer sequence A=(A_1,A_2,\dots,A_N) of length N.
Find the number of triples of integers (i,j,k) that satisfy all of the following:

• 1 \le i,j,k \le N
• A_i : A_j : A_k = 7:5:3
• \min(i,j,k) = j or \max(i,j,k) = j.

Constraints

• All input values are integers.
• 1 \le N \le 3 \times 10^5
• 1 \le A_i \le 10^9

Sample Input 1

10
3 10 7 10 7 6 7 6 5 14

Sample Output 1

7

The seven triples of integers (i,j,k) that satisfy the conditions are:

• (3,9,1)
  • A_i : A_j : A_k = 7:5:3, and \max(i,j,k) = j.
• (5,9,1)
  • A_i : A_j : A_k = 7:5:3, and \max(i,j,k) = j.
• (7,9,1)
  • A_i : A_j : A_k = 7:5:3, and \max(i,j,k) = j.
• (10,2,6)
  • A_i : A_j : A_k = 14:10:6 = 7:5:3, and \min(i,j,k) = j.
• (10,2,8)
  • A_i : A_j : A_k = 14:10:6 = 7:5:3, and \min(i,j,k) = j.
• (10,4,6)
  • A_i : A_j : A_k = 14:10:6 = 7:5:3, and \min(i,j,k) = j.
• (10,4,8)
  • A_i : A_j : A_k = 14:10:6 = 7:5:3, and \min(i,j,k) = j.

Sample Input 2

6
210 210 210 210 210 210

Sample Output 2

0

Sample Input 3

21
49 30 50 21 35 15 21 70 35 9 50 70 21 49 30 50 70 15 9 21 30

Sample Output 3

34

Problem Statement

Happy New Year! When it comes to outdoor play on New Year's, it's kite flying!

N people numbered 1 to N are trying to fly kites by the riverbank.
The river facing the riverbank flows in a straight line, so from now on, we consider a two-dimensional coordinate system where the x-axis is the direction of the river and the y-axis is the height direction.
Person i is standing at point (A_i, 0) and trying to fly a kite at point (B_i, 1).
However, to avoid collisions of people and kites, and to avoid kite strings getting tangled, persons i and j (i \neq j) cannot fly kites at the same time if the following condition is satisfied:

• The "line segment connecting (A_i, 0) and (B_i, 1)" and the "line segment connecting (A_j, 0) and (B_j, 1)" have an intersection point. (This includes the case where the endpoints of the line segments touch each other.)

What is the maximum number of people who can fly kites at the same time while respecting the above constraint?

Constraints

• 1 \leq N \leq 2\times 10^5
• 0 \leq A_i \leq 10^9
• 0 \leq B_i \leq 10^9
• All input values are integers.

Sample Input 1

3
3 5
1 4
2 6

Sample Output 1

2

Persons 1 and 2, as well as persons 2 and 3, can fly kites at the same time, but persons 1 and 3 cannot fly kites at the same time.
Therefore, two people, if chosen appropriately, can fly kites at the same time, while it is impossible for three people to fly kites at the same time. Thus, the answer is 2.

Sample Input 2

5
1 2
1 3
1 4
1 5
1 6

Sample Output 2

1

Sample Input 3

10
440423913 766294629
725560240 59187619
965580535 585990756
550925213 623321125
549392044 122410708
21524934 690874816
529970099 244587368
757265587 736247509
576136367 993115118
219853537 21553211

Sample Output 3

4

Problem Statement

A sequence a=(a_1,a_2,\dots,a_k) of length k is defined to be kadomatsu-like as follows:

• Let x be the number of integers i that satisfy 2 \le i \le k-1, a_{i-1} < a_i, and a_i > a_{i+1}.
• Let y be the number of integers i that satisfy 2 \le i \le k-1, a_{i-1} > a_i, and a_i < a_{i+1}.
• The sequence a is called kadomatsu-like if and only if x > y.

You are given a permutation P of (1,2,\dots,N).
Find the number, modulo 998244353, of (not necessarily contiguous) subsequences of P that are kadomatsu-like.

Constraints

• All input values are integers.
• 1 \le N \le 3 \times 10^5
• P is a permutation of (1,2,\dots,N).

Sample Input 1

4
1 3 4 2

Sample Output 1

4

Among the subsequences of P, the following four are kadomatsu-like:

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

Sample Input 2

1
1

Sample Output 2

0

Sample Input 3

20
11 10 18 13 12 16 5 19 7 6 17 4 9 1 14 2 20 15 8 3

Sample Output 3

431610

For example, the subsequence a=(10,13,12,5,7,9,20,3) is kadomatsu-like.

• We have a_{i-1} < a_i and a_i > a_{i+1} for i=2,7, so x=2.
• We have a_{i-1} > a_i and a_i < a_{i+1} for i=4, so y=1.
• Since x > y, the subsequence a is kadomatsu-like.

Problem Statement

Happy New Year! When it comes to indoor play on New Year's, it's sugoroku!

There is a sugoroku board consisting of N+1 squares: squares 0, square 1, \dots, square N.
There is an M-sided die (dice) that produces positive integers A_1, A_2, \dots, A_M with equal probability. Here, A_1, A_2, \dots, A_M are distinct.
Person 1, person 2, \dots, person L will play a game using this board. The game proceeds as follows:

• Initially, place L pieces, piece 1, piece 2, \dots, piece L, on square 0.
• Turns come around in numerical order starting with person 1. Strictly speaking, after person i's turn, the turn goes to person (i \bmod L) + 1. Each person performs the following operation on their turn:
  • Let i be the number of the person whose turn it is. Roll the die. Let x be the square where piece i is located and y be the integer that came up on the die, and move piece i to square \min(N, x+y).
• The first person to place their numbered piece on square N wins, and the other people lose.

For i =1,2,\dots,L, find the probability, modulo 998244353, that person i wins.

Constraints

• 1 \leq N \leq 2.5 \times 10^5
• 1 \leq M \leq N
• 2 \leq L \leq 2.5 \times 10^5
• 1 \leq A_1 \lt A_2 \lt \dots \lt A_M \leq N
• All input values are integers.

Sample Input 1

2 2 3
1 2

Sample Output 1

374341633
748683265
873463809

Person 1 wins with the probability \frac{5}{8}, person 2 wins with the probability \frac{1}{4}, and person 3 wins with the probability \frac{1}{8}.

Sample Input 2

100 2 4
20 26

Sample Output 2

164734081
939753473
943409153
946836353

Sample Input 3

123456 12 10
21994 29598 47718 59035 69293 73766 74148 76721 98917 104184 120533 122441

Sample Output 3

580013367
81975961
178650340
610261473
14826260
541995390
307779600
913805572
76177928
687491522