Your task is to calculate the number of arrays such that:
- each array contains $n$ elements;
- each element is an integer from $1$ to $m$;
- for each array, there is exactly one pair of equal elements;
- for each array $a$, there exists an index $i$ such that the array is strictly ascending before the $i$-th element and strictly descending after it (formally, it means that $a_j < a_{j + 1}$, if $j < i$, and $a_j > a_{j + 1}$, if $j \ge i$).
Input
The first line contains two integers $n$ and $m$ ($2 \le n \le m \le 2 \cdot 10^5$).
Output
Print one integer — the number of arrays that meet all of the aforementioned conditions, taken modulo $998244353$.
Examples
input
3 4
output
6
input
3 5
output
10
input
42 1337
output
806066790
input
100000 200000
output
707899035
Note
The arrays in the first example are:
- $[1, 2, 1]$;
- $[1, 3, 1]$;
- $[1, 4, 1]$;
- $[2, 3, 2]$;
- $[2, 4, 2]$;
- $[3, 4, 3]$.
Solution:
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=998244353;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
int n,m;
ll ans=1,r=1;
int main() {
scanf("%d%d",&n,&m);
if (n==2) {
puts("0");
return 0;
}
for (int i=1;i<=m;i++) ans=ans*i%mod;
for (int i=1;i<=n-1;i++) r=r*i%mod;
for (int i=1;i<=m-n+1;i++) r=r*i%mod;
ans=ans*powmod(r,mod-2)%mod*(n-2)%mod;
ans=ans*powmod(2,n-3)%mod;
printf("%lld\n",ans);
}
