-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathCountTheArrays.java
More file actions
63 lines (62 loc) · 1.42 KB
/
CountTheArrays.java
File metadata and controls
63 lines (62 loc) · 1.42 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
import java.io.*;
public class CountTheArrays {
static final int mod = 998244353;
static long[] factorials;
static int M;
static int N;
public static void main(String[] args) throws IOException
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] temp = br.readLine().split(" ");
N = Integer.parseInt(temp[0]);
M = Integer.parseInt(temp[1]);
factorials = new long[M+1];
fact();
long tot = choose(M, N-1);
tot *= (N-2);
tot %= mod;
tot *= binpow(2, N-3);
tot %= mod;
System.out.println(tot);
br.close();
}
public static void fact() // one-indexed factorial table
{
factorials[0] = 1;
for (int i = 1; i < factorials.length; i++)
factorials[i] = (factorials[i-1] * i ) % mod;
}
public static long inv(long a) //fermat's little theorem
{
return binpow(a, mod-2);
}
public static long div(long a, long b) // modular division
{
return (a * inv(b))%mod;
}
public static long mult(long a, long b) // modular multiplication
{
return (a * b)%mod;
}
public static long binpow(long a, long b) // binary exponentiation
{
long res = 1;
long multiply = a;
while (b > 0)
{
if ((b & 1) == 1)
{
res *= multiply;
res %= mod;
}
multiply = multiply*multiply;
multiply %= mod;
b >>= 1;
}
return res;
}
public static long choose(int n, int k) // combinations
{
return ((factorials[n]%mod)*inv((factorials[n-k]*factorials[k])%mod))%mod;
}
}