Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 900 点
問題文
周長 L の円があり,円周上に L 人の人が等間隔に立っています. 彼らを時計回りに人 0,1,\cdots,L-1 と呼ぶことにします. この L 人から N 人を選ぶことを考えます. ある選び方のコストを以下のように定義します.
- N 人から 2 人組を選ぶすべての方法について,一方の人が他方の人の位置まで (円周上のみを通って) 移動するときの最小の移動距離を求める. これらの距離の最大値がコストとなる.
すべての選び方に対するコストの総和を 998244353 で割ったあまりを求めてください.
制約
- 2 \leq N \leq L \leq 10^6
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる.
L N
出力
答えを出力せよ.
入力例 1
4 2
出力例 1
8
選んだ N 人と,それに対応するコストは以下の通りです.
- (0,1): コスト 1
- (0,2): コスト 2
- (0,3): コスト 1
- (1,2): コスト 1
- (1,3): コスト 2
- (2,3): コスト 1
これらの総和である 8 が答えになります.
入力例 2
5 5
出力例 2
2
全員を選ぶしかありません. このときのコストは 2 です.
入力例 3
13 5
出力例 3
7618
入力例 4
1000000 100000
出力例 4
664396470
Score : 900 points
Problem Statement
There is a circle with circumference L, and L people are standing equally spaced along the circumference. They are labeled as person 0, 1, \cdots, L-1 in clockwise order. Consider choosing N from these L people. The cost of a choice is defined as follows.
- For every pair of persons among the N chosen people, find the minimum distance one person has to move along the circumference to reach the other person's position. The maximum value among these distances is the cost.
Find the sum of costs over all possible choices, modulo 998244353.
Constraints
- 2 \leq N \leq L \leq 10^6
- All input values are integers.
Input
The input is given from Standard Input in the following format:
L N
Output
Print the answer.
Sample Input 1
4 2
Sample Output 1
8
The choices of N people and their corresponding costs are as follows:
- (0,1): cost 1
- (0,2): cost 2
- (0,3): cost 1
- (1,2): cost 1
- (1,3): cost 2
- (2,3): cost 1
The sum of these costs, 8, is the answer.
Sample Input 2
5 5
Sample Output 2
2
We can only choose all of them. In this case, the cost is 2.
Sample Input 3
13 5
Sample Output 3
7618
Sample Input 4
1000000 100000
Sample Output 4
664396470
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 900 点
問題文
0
,1
のみからなる文字列の組 (S,T) が次の条件をすべて満たすとき (そしてそのときのみ) それを良い文字列組と呼ぶことにします.
- S,T に含まれる
0
の個数は等しい. - S,T に含まれる
1
の個数は等しい.
特に,良い文字列組 (S,T) について,S,T の長さは同じです.
良い文字列組 (S,T) に対し,無向グラフ G(S,T) を次のように定義します.
- S の長さを L とする.頂点 1,2,\cdots,L からなるグラフ g をつくる.
- S に含まれる
0
の個数を n とする. S に含まれる0
の index を 1 \leq a_1 < a_2 < \cdots < a_n \leq L とする. T に含まれる0
の index を 1 \leq b_1 < b_2 < \cdots < b_n \leq L とする. 各 1 \leq i \leq n に対し,頂点 a_i と頂点 b_i を結ぶ辺を g に追加する. - S に含まれる
1
の個数を m とする. S に含まれる1
の index を 1 \leq c_1 < c_2 < \cdots < c_m \leq L とする. T に含まれる1
の index を 1 \leq d_1 < d_2 < \cdots < d_m \leq L とする. 各 1 \leq i \leq m に対し,頂点 c_i と頂点 d_i を結ぶ辺を g に追加する. - 以上の手順で得た g を G(S,T) とする.
長さ N の整数列 A=(A_1,A_2,\cdots,A_N) が与えられます. 以下の条件をすべて満たす良い文字列組 (S,T) を 1 つ見つけてください.
- S の長さを L とする.N \leq L \leq 10^5 である.
- 各 1 \leq i,j \leq N について,G(S,T) で頂点 i と頂点 j が同じ連結成分に属すとき,そしてそのときのみ A_i=A_j である.
なお,この問題の制約下で解が必ず存在することが証明できます.
制約
- 1 \leq N \leq 100
- 1 \leq A_i \leq N
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる.
N A_1 A_2 \cdots A_N
出力
答えを以下の形式で出力せよ.
L S T
ここで,L は S,T の長さである. 解が複数存在する場合,どれを出力しても構わない.
入力例 1
3 1 2 1
出力例 1
4 0011 1100
出力例の S,T について G(S,T) を求めると,次のようになります.
- 4 頂点ならなるグラフ g を用意する.
- S に含まれる
0
の index は (1,2) で,T に含まれる0
の index は (3,4) である. 辺 (1,3),(2,4) を g に追加する. - S に含まれる
1
の index は (3,4) で,T に含まれる1
の index は (1,2) である. 辺 (3,1),(4,2) を g に追加する. - G(S,T)=g とする.
G(S,T) の連結成分は,頂点 (1,3) からなる成分と頂点 (2,4) からなる成分です. これは条件をすべて満たすので,この (S,T) は正しい出力です.
入力例 2
5 1 2 3 4 5
出力例 2
5 01010 01010
入力例 3
6 1 1 1 1 1 1
出力例 3
6 011111 111110
入力例 4
10 1 2 3 2 4 3 4 4 5 6
出力例 4
21 000101010111100011011 011010000010101111110
Score : 900 points
Problem Statement
A pair of strings (S, T) consisting of 0
and 1
is called good if and only if all of the following conditions are satisfied.
- S and T contain the same number of
0
s. - S and T contain the same number of
1
s.
Particularly, for a good string pair (S, T), S and T have the same length.
For a good string pair (S, T), we define an undirected graph G(S, T) as follows.
- Let L be the length of S. Create a graph g with vertices 1, 2, \cdots, L.
- Let n be the number of
0
s in S. Let the indices of0
s in S be 1 \leq a_1 < a_2 < \cdots < a_n \leq L. Let the indices of0
s in T be 1 \leq b_1 < b_2 < \cdots < b_n \leq L. For each 1 \leq i \leq n, add an edge between vertices a_i and b_i to g. - Let m be the number of
1
s in S. Let the indices of1
s in S be 1 \leq c_1 < c_2 < \cdots < c_m \leq L. Let the indices of1
s in T be 1 \leq d_1 < d_2 < \cdots < d_m \leq L. For each 1 \leq i \leq m, add an edge between vertices c_i and d_i to g. - The graph g obtained through the above steps is G(S, T).
You are given an integer sequence A = (A_1, A_2, \cdots, A_N) of length N. Find one good string pair (S, T) satisfying all of the following conditions.
- Let L be the length of S. It satisfies N \leq L \leq 10^5.
- For each pair 1 \leq i, j \leq N, vertices i and j belong to the same connected component in G(S, T) if and only if A_i = A_j.
It can be proved that a solution always exists under the constraints of this problem.
Constraints
- 1 \leq N \leq 100
- 1 \leq A_i \leq N
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \cdots A_N
Output
Print a solution in the following format:
L S T
Here, L is the length of S and T. If multiple solutions exist, any of them will be accepted.
Sample Input 1
3 1 2 1
Sample Output 1
4 0011 1100
For the S and T in the sample output, we obtain G(S, T) as follows:
- Prepare a graph g with 4 vertices.
- The indices of
0
s in S are (1, 2), and the indices of0
s in T are (3, 4). Add edges (1, 3) and (2, 4) to g. - The indices of
1
s in S are (3, 4), and the indices of1
s in T are (1, 2). Add edges (3, 1) and (4, 2) to g. - Let G(S, T) = g.
G(S, T) has a connected component with vertices (1, 3) and another with vertices (2, 4). This satisfies all the conditions, so this (S, T) is a valid output.
Sample Input 2
5 1 2 3 4 5
Sample Output 2
5 01010 01010
Sample Input 3
6 1 1 1 1 1 1
Sample Output 3
6 011111 111110
Sample Input 4
10 1 2 3 2 4 3 4 4 5 6
Sample Output 4
21 000101010111100011011 011010000010101111110
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1200 点
問題文
1 から N までの番号がついた N 個の箱と,1 から N までの番号がついた N 個のボールがあります.
あなたはすぬけくんに対し,宿題として以下の手順を行うことを課しました.
- それぞれのボールを好きな箱に入れる.1 つの箱に複数のボールが入ってもよいし,ボールが入らない箱があってもよい.
- i=1,2,\cdots,N に対してこの順に以下の操作を行う.
- 箱 i にボールが入っていない場合,何もしない.
- 箱 i にボールが入っている場合,それらをすべて取り出し,好きな順番で一列に並べる.取り出したボールの個数を k ,列の中のボールの番号を (x_1,x_2,\cdots,x_k) とする.各 1 \leq j \leq k に対して,ボール x_j を箱 x_{j+1} に入れる.ただしここで x_{k+1} は x_1 を意味する. ボールを箱に入れる操作はすべて同時に行うものとする.
すぬけくんは宿題を終えたと主張し,最終状態をあなたに報告してきました. 具体的には,手順の終了後,ボール i が箱 A_i に入っている状態になったと言っています.
あなたは,すぬけくんが手順を正しく行ったかどうかを疑っています. すぬけくんが報告した状態が手順の結果としてあり得るかどうかを判定してください.
1 つの入力につきテストケースは T 個あります.
制約
- 1 \leq T \leq 250000
- 1 \leq N \leq 250000
- 1 \leq A_i \leq N
- ひとつの入力の中のテストケースすべてにわたる N の総和は 250000 以下である
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる.
T case_1 case_2 \vdots case_T
各テストケースは以下の形式で与えられる.
N A_1 A_2 \cdots A_N
出力
各テストケースに対し,すぬけくんが報告した状態が手順の結果としてあり得るならば Yes
,あり得ないならば No
を出力せよ.
入力例 1
5 3 1 1 1 3 2 2 2 5 1 2 3 4 5 10 8 3 8 10 1 5 3 1 6 4 10 1 5 1 2 4 8 8 6 7 3
出力例 1
Yes No Yes No Yes
1 つめのテストケースについて考えます.
以下の手順を考えるとすぬけくんが報告した状態になるので,答えは Yes
です.
- ボール 1,2,3 をそれぞれ箱 1,1,2 に入れる.
- 箱 1 のボールを取り出して,(2,1) と並べる.
- ボール 2 を箱 1 に入れる.
- ボール 1 を箱 2 に入れる.
- 箱 2 のボールを取り出して,(1,3) と並べる.
- ボール 1 を箱 3 に入れる.
- ボール 3 を箱 1 に入れる.
- 箱 3 のボールを取り出して,(1) と並べる.
- ボール 1 を箱 1 に入れる.
- ボール 1,2,3 がそれぞれ箱 1,1,1 に入っている状態になる.
Score : 1200 points
Problem Statement
There are N boxes numbered from 1 to N, and N balls numbered from 1 to N.
You have assigned Snuke the following procedure as homework.
- Put each ball into any box he likes. Multiple balls can be placed in the same box, and there can be boxes without balls.
- For i = 1, 2, \cdots, N in this order, perform the following operations.
- If box i contains no balls, do nothing.
- If box i contains balls, take all of them out and arrange them in a line in any order he likes. Let k be the number of balls taken out, and (x_1, x_2, \cdots, x_k) be the ball numbers in the line. For each 1 \leq j \leq k, put ball x_j into box x_{j+1}. Here, x_{k+1} means x_1. All these operations of putting balls into boxes happen simultaneously.
He claims that he has completed the homework and reports the final state to you. Specifically, he says that ball i is in box A_i after the procedure.
You doubt whether he has correctly performed the procedure. Determine whether the state he reported is a possible result of the procedure.
There are T test cases for each input.
Constraints
- 1 \leq T \leq 250000
- 1 \leq N \leq 250000
- 1 \leq A_i \leq N
- The sum of N over all test cases in each input is at most 250000.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T case_1 case_2 \vdots case_T
Each test case is given in the following format:
N A_1 A_2 \cdots A_N
Output
For each test case, print Yes
if the state Snuke reported is a possible result of the procedure, and No
otherwise.
Sample Input 1
5 3 1 1 1 3 2 2 2 5 1 2 3 4 5 10 8 3 8 10 1 5 3 1 6 4 10 1 5 1 2 4 8 8 6 7 3
Sample Output 1
Yes No Yes No Yes
Consider the first test case.
The following steps yield the state Snuke reported, so the answer is Yes
.
- Put balls 1, 2, 3 into boxes 1, 1, 2, respectively.
- Take out the balls from box 1 and arrange them as (2, 1).
- Put ball 2 into box 1.
- Put ball 1 into box 2.
- Take out the balls from box 2 and arrange them as (1, 3).
- Put ball 1 into box 3.
- Put ball 3 into box 1.
- Take out the balls from box 3 and arrange them as (1).
- Put ball 1 into box 1.
- Now, balls 1, 2, 3 are all in box 1.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1200 点
問題文
1 から N までの番号がついた N 頂点からなる根付き木 T があります. 頂点 1 が根で,頂点 i (2 \leq i \leq N) の親は P_i (P_i < i) です.
(1,2,\cdots,N) の順列 x=(x_1,x_2,\cdots,x_N) が良い順列か否かは,以下の手順で判定されます.
- x に対する次の操作を考える.
- x の隣接する 2 要素 u,v であって,u,v が T 上で先祖子孫の関係にあるものを選ぶ.u,v のどちらが先祖でどちらが子孫でも構わない.そして,u,v を swap する.
- 上記の操作を 0 回以上行い,初期状態よりも辞書順で真に小さい順列を得ることが可能ならば,x は良い順列ではない.どう操作しても初期状態よりも辞書順で真に小さい順列が得られないなら,x は良い順列である.
正整数 B が与えられます. 順列 x に対し,\operatorname{hash}(x)=\sum_{1 \leq i \leq N} B^{i-1} \times x_i と定義します.
良い順列 x すべてに対する \operatorname{hash}(x) の総和を 998244353 で割ったあまりを求めてください.
数列の辞書順とは?
数列 S = (S_1,S_2,\ldots,S_{|S|}) が数列 T = (T_1,T_2,\ldots,T_{|T|}) より辞書順で小さいとは,下記の 1. と 2. のどちらかが成り立つことを言います. ここで,|S|, |T| はそれぞれ S, T の長さを表します.
- |S| \lt |T| かつ (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}).
- ある整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace が存在して,下記の 2 つがともに成り立つ.
- (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})
- S_i が T_i より(数として)小さい.
制約
- 2 \leq N \leq 100
- 1 \leq B < 998244353
- 1 \leq P_i < i (2 \leq i \leq N)
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる.
N B P_2 P_3 \cdots P_N
出力
答えを出力せよ.
入力例 1
3 100 1 1
出力例 1
50502
例えば,x=(3,1,2) は良い順列ではありません. これは先祖子孫の関係にある 3,1 を swap することで (1,3,2) というより小さい順列が得られるからです.
このサンプルでは,良い順列は x=(1,2,3),(1,3,2) の 2 つです. よって,\operatorname{hash}((1,2,3))+\operatorname{hash}((1,3,2))=30201+20301=50502 が答えになります.
入力例 2
5 100 1 2 3 4
出力例 2
504030201
このサンプルでは,どの 2 頂点をとってもそれらは先祖子孫の関係にあります. よって良い順列は x=(1,2,3,4,5) のみです.
入力例 3
10 248730679 1 2 1 2 5 6 1 8 1
出力例 3
856673861
入力例 4
20 480124393 1 2 3 2 3 4 3 8 3 4 11 10 4 14 15 12 17 18 19
出力例 4
488941820
Score : 1200 points
Problem Statement
There is a rooted tree T with N vertices numbered from 1 to N. Vertex 1 is the root, and the parent of vertex i (2 \leq i \leq N) is P_i (P_i < i).
A permutation x = (x_1, x_2, \cdots, x_N) of (1, 2, \cdots, N) is judged to be a good permutation or not by the following criteria.
- Consider the following operation on x.
- Choose two adjacent elements u and v in x such that u and v are in an ancestor-descendant relationship in T. It does not matter which is the ancestor and which is the descendant. Then, swap u and v.
- If it is possible to obtain a permutation that is lexicographically strictly smaller than the initial state by performing the above operation zero or more times, x is not a good permutation. If it is impossible to obtain a permutation lexicographically smaller than the initial state by any such operations, x is a good permutation.
You are given a positive integer B. For a permutation x, define \operatorname{hash}(x) = \sum_{1 \leq i \leq N} B^{i-1} \times x_i.
Find the sum of \operatorname{hash}(x) over all good permutations x, modulo 998244353.
What is lexicographical order on sequences?
A sequence S = (S_1, S_2, \ldots, S_{|S|}) is said to be lexicographically smaller than a sequence T = (T_1, T_2, \ldots, T_{|T|}) if and only if 1. or 2. below holds. Here, |S| and |T| denote the lengths of S and T, respectively.
- |S| \lt |T| and (S_1, S_2, \ldots, S_{|S|}) = (T_1, T_2, \ldots, T_{|S|}).
- There exists an integer 1 \leq i \leq \min\{ |S|, |T| \} such that the following two statements hold.
- (S_1, S_2, \ldots, S_{i-1}) = (T_1, T_2, \ldots, T_{i-1}).
- S_i is smaller than T_i (as a number).
Constraints
- 2 \leq N \leq 100
- 1 \leq B < 998244353
- 1 \leq P_i < i (2 \leq i \leq N)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N B P_2 P_3 \cdots P_N
Output
Print the answer.
Sample Input 1
3 100 1 1
Sample Output 1
50502
For example, x = (3, 1, 2) is not a good permutation, because by swapping 3 and 1, which are in an ancestor-descendant relationship, we can obtain (1, 3, 2), a lexicographically smaller permutation.
In this sample, the good permutations are x = (1, 2, 3) and x = (1, 3, 2). Thus, the answer is \operatorname{hash}((1,2,3)) + \operatorname{hash}((1,3,2)) = 30201 + 20301 = 50502.
Sample Input 2
5 100 1 2 3 4
Sample Output 2
504030201
In this sample, any two vertices are in an ancestor-descendant relationship. Therefore, the only good permutation is x = (1, 2, 3, 4, 5).
Sample Input 3
10 248730679 1 2 1 2 5 6 1 8 1
Sample Output 3
856673861
Sample Input 4
20 480124393 1 2 3 2 3 4 3 8 3 4 11 10 4 14 15 12 17 18 19
Sample Output 4
488941820
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1200 点
問題文
N \times N の整数行列 A=(A_{i,j})_{1 \leq i \leq N,1 \leq j \leq N},及び整数 M が与えられます.
1 以上 N 以下の整数からなる長さ M の整数列 x=(x_1,x_2,\cdots,x_M) に対し,f(x) を次のように定義します.
- x の要素を広義単調増加になるようソートしたあとの列を y=(y_1,y_2,\cdots,y_M) とおく.
- f(x)=\prod_{1 \leq i \leq M} A_{x_i,y_i} と定義する.
各 k=1,2,\cdots,N について,次の問題を解いてください.
- x_1=k を満たす x すべてに対する f(x) の値の総和を 998244353 で割ったあまりを求めよ.
制約
- 1 \leq N \leq 50
- 1 \leq M \leq 50
- 0 \leq A_{i,j} < 998244353
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる.
N M A_{1,1} A_{1,2} \cdots A_{1,N} A_{2,1} A_{2,2} \cdots A_{2,N} \vdots A_{N,1} A_{N,2} \cdots A_{N,N}
出力
k=1,2,\cdots,N に対する答えをこの順に出力せよ.
入力例 1
2 2 1 2 3 4
出力例 1
5 22
すべての x とそれに対する f(x) の値は以下のとおりです.
- x=(1,1): y=(1,1), f(x)=A_{1,1} \times A_{1,1}=1
- x=(1,2): y=(1,2), f(x)=A_{1,1} \times A_{2,2}=4
- x=(2,1): y=(1,2), f(x)=A_{2,1} \times A_{1,2}=6
- x=(2,2): y=(2,2), f(x)=A_{2,2} \times A_{2,2}=16
よって k=1 に対する答えは 1+4=5 で,k=2 に対する答えは 6+16=22 です.
入力例 2
2 3 1 2 3 4
出力例 2
27 118
入力例 3
5 4 785439575 250040585 709423541 945005786 19237225 404191279 250876592 22672563 519729086 344065186 273714212 560047125 139793596 542901248 520999410 855572558 498896932 418633758 742973826 248730678 238856535 319502970 908902333 164543594 245101681
出力例 3
216530400 726773157 717209375 797938347 957133905
入力例 4
10 50 197971506 714635866 966125570 768080799 80565655 459117401 256810168 775681305 582857561 948631706 437330820 321722967 531470304 255908811 45459908 504089816 695016247 91058795 905527130 30860430 151769562 979797105 619322493 298241991 360690308 480124392 297323928 284686636 922571073 627798362 753705854 712639027 721488863 69714419 485979799 88704853 758288417 423073188 595934547 86264514 272481811 622712481 221745114 225051881 433378197 985573661 210619166 851716760 283615535 834897126 366075547 933505674 858395194 490049033 22039836 361481447 735151983 518458804 422209788 28981946 907645400 111982636 978445563 686621115 486475154 734616351 587635888 527524079 454844580 826849288 868863954 490627044 967828344 887235558 138021910 435784230 343307056 118718683 547282350 757693154 32344652 101428952 585897722 693817619 790433406 848494439 873744405 604427602 951889915 989125209 865548541 642980476 603592935 911086893 466178404 79002814 902745597 825893950 147052664 805753279
出力例 4
862518623 606960987 762676180 606184511 762408948 47716007 968649097 788324707 140177479 484063588
Score : 1200 points
Problem Statement
You are given an N \times N integer matrix A = (A_{i,j})_{1 \leq i \leq N, 1 \leq j \leq N} and an integer M.
For an integer sequence x = (x_1, x_2, \cdots, x_M) of length M consisting of integers between 1 and N, inclusive, define f(x) as follows:
- Let y = (y_1, y_2, \cdots, y_M) be the sequence obtained by sorting the elements of x to be non-decreasing.
- Define f(x) = \prod_{1 \leq i \leq M} A_{x_i, y_i}.
For each k = 1, 2, \cdots, N, solve the following problem:
- Find the sum of f(x) over all sequences x satisfying x_1 = k, modulo 998244353.
Constraints
- 1 \leq N \leq 50
- 1 \leq M \leq 50
- 0 \leq A_{i,j} < 998244353
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M A_{1,1} A_{1,2} \cdots A_{1,N} A_{2,1} A_{2,2} \cdots A_{2,N} \vdots A_{N,1} A_{N,2} \cdots A_{N,N}
Output
Print the answer for each k = 1, 2, \cdots, N in this order.
Sample Input 1
2 2 1 2 3 4
Sample Output 1
5 22
All possible x and the corresponding values of f(x) are as follows.
- x = (1, 1): y = (1, 1), f(x) = A_{1,1} \times A_{1,1} = 1
- x = (1, 2): y = (1, 2), f(x) = A_{1,1} \times A_{2,2} = 4
- x = (2, 1): y = (1, 2), f(x) = A_{2,1} \times A_{1,2} = 6
- x = (2, 2): y = (2, 2), f(x) = A_{2,2} \times A_{2,2} = 16
Thus, the answer is 1 + 4 = 5 for k = 1, and 6 + 16 = 22 for k = 2.
Sample Input 2
2 3 1 2 3 4
Sample Output 2
27 118
Sample Input 3
5 4 785439575 250040585 709423541 945005786 19237225 404191279 250876592 22672563 519729086 344065186 273714212 560047125 139793596 542901248 520999410 855572558 498896932 418633758 742973826 248730678 238856535 319502970 908902333 164543594 245101681
Sample Output 3
216530400 726773157 717209375 797938347 957133905
Sample Input 4
10 50 197971506 714635866 966125570 768080799 80565655 459117401 256810168 775681305 582857561 948631706 437330820 321722967 531470304 255908811 45459908 504089816 695016247 91058795 905527130 30860430 151769562 979797105 619322493 298241991 360690308 480124392 297323928 284686636 922571073 627798362 753705854 712639027 721488863 69714419 485979799 88704853 758288417 423073188 595934547 86264514 272481811 622712481 221745114 225051881 433378197 985573661 210619166 851716760 283615535 834897126 366075547 933505674 858395194 490049033 22039836 361481447 735151983 518458804 422209788 28981946 907645400 111982636 978445563 686621115 486475154 734616351 587635888 527524079 454844580 826849288 868863954 490627044 967828344 887235558 138021910 435784230 343307056 118718683 547282350 757693154 32344652 101428952 585897722 693817619 790433406 848494439 873744405 604427602 951889915 989125209 865548541 642980476 603592935 911086893 466178404 79002814 902745597 825893950 147052664 805753279
Sample Output 4
862518623 606960987 762676180 606184511 762408948 47716007 968649097 788324707 140177479 484063588