Problem Statement

Compute A \times B.

Constraints

• 1 \leq A \leq 100
• 1 \leq B \leq 100
• All values in input are integers.

Sample Input 1

2 5

Sample Output 1

10

We have 2 \times 5 = 10.

Sample Input 2

100 100

Sample Output 2

10000

Problem Statement

Given N integers A_1, ..., A_N, compute A_1 \times ... \times A_N.

However, if the result exceeds 10^{18}, print -1 instead.

Constraints

• 2 \leq N \leq 10^5
• 0 \leq A_i \leq 10^{18}
• All values in input are integers.

Sample Input 1

2
1000000000 1000000000

Sample Output 1

1000000000000000000

We have 1000000000 \times 1000000000 = 1000000000000000000.

Sample Input 2

3
101 9901 999999000001

Sample Output 2

-1

We have 101 \times 9901 \times 999999000001 = 1000000000000000001, which exceeds 10^{18}, so we should print -1 instead.

Sample Input 3

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

Sample Output 3

0

Problem Statement

Compute A \times B, truncate its fractional part, and print the result as an integer.

Constraints

• 0 \leq A \leq 10^{15}
• 0 \leq B < 10
• A is an integer.
• B is a number with two digits after the decimal point.

Sample Input 1

198 1.10

Sample Output 1

217

We have 198 \times 1.10 = 217.8. After truncating the fractional part, we have the answer: 217.

Sample Input 2

1 0.01

Sample Output 2

0

Sample Input 3

1000000000000000 9.99

Sample Output 3

9990000000000000

Problem Statement

Given is a positive integer N. Consider repeatedly applying the operation below on N:

• First, choose a positive integer z satisfying all of the conditions below:
  • z can be represented as z=p^e, where p is a prime number and e is a positive integer;
  • z divides N;
  • z is different from all integers chosen in previous operations.
• Then, replace N with N/z.

Find the maximum number of times the operation can be applied.

Constraints

• All values in input are integers.
• 1 \leq N \leq 10^{12}

Sample Input 1

24

Sample Output 1

3

We can apply the operation three times by, for example, making the following choices:

• Choose z=2 (=2^1). (Now we have N=12.)
• Choose z=3 (=3^1). (Now we have N=4.)
• Choose z=4 (=2^2). (Now we have N=1.)

Sample Input 2

1

Sample Output 2

0

We cannot apply the operation at all.

Sample Input 3

64

Sample Output 3

3

We can apply the operation three times by, for example, making the following choices:

• Choose z=2 (=2^1). (Now we have N=32.)
• Choose z=4 (=2^2). (Now we have N=8.)
• Choose z=8 (=2^3). (Now we have N=1.)

Sample Input 4

1000000007

Sample Output 4

1

We can apply the operation once by, for example, making the following choice:

• z=1000000007 (=1000000007^1). (Now we have N=1.)

Sample Input 5

997764507000

Sample Output 5

7

Problem Statement

There are N integers X_1, X_2, \cdots, X_N, and we know that A_i \leq X_i \leq B_i. Find the number of different values that the median of X_1, X_2, \cdots, X_N can take.

Notes

The median of X_1, X_2, \cdots, X_N is defined as follows. Let x_1, x_2, \cdots, x_N be the result of sorting X_1, X_2, \cdots, X_N in ascending order.

• If N is odd, the median is x_{(N+1)/2};
• if N is even, the median is (x_{N/2} + x_{N/2+1}) / 2.

Constraints

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

Sample Input 1

2
1 2
2 3

Sample Output 1

3

• If X_1 = 1 and X_2 = 2, the median is \frac{3}{2};

• if X_1 = 1 and X_2 = 3, the median is 2;

• if X_1 = 2 and X_2 = 2, the median is 2;

• if X_1 = 2 and X_2 = 3, the median is \frac{5}{2}.

Thus, the median can take three values: \frac{3}{2}, 2, and \frac{5}{2}.

Sample Input 2

3
100 100
10 10000
1 1000000000

Sample Output 2

9991

Problem Statement

Given are a sequence of N positive integers A_1, A_2, \ldots, A_N and another positive integer S.
For a non-empty subset T of the set \{1, 2, \ldots , N \}, let us define f(T) as follows:

• f(T) is the number of different non-empty subsets \{x_1, x_2, \ldots , x_k \} of T such that A_{x_1}+A_{x_2}+\cdots +A_{x_k} = S.

Find the sum of f(T) over all 2^N-1 subsets T of \{1, 2, \ldots , N \}. Since the sum can be enormous, print it modulo 998244353.

Constraints

• All values in input are integers.
• 1 \leq N \leq 3000
• 1 \leq S \leq 3000
• 1 \leq A_i \leq 3000

Sample Input 1

3 4
2 2 4

Sample Output 1

6

For each T, the value of f(T) is shown below. The sum of these values is 6.

• f(\{1\}) = 0
• f(\{2\}) = 0
• f(\{3\}) = 1 (One subset \{3\} satisfies the condition.)
• f(\{1, 2\}) = 1 (\{1, 2\})
• f(\{2, 3\}) = 1 (\{3\})
• f(\{1, 3\}) = 1 (\{3\})
• f(\{1, 2, 3\}) = 2 (\{1, 2\}, \{3\})

Sample Input 2

5 8
9 9 9 9 9

Sample Output 2

0

Sample Input 3

10 10
3 1 4 1 5 9 2 6 5 3

Sample Output 3

3296