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); }
Related posts:
Intersecting Subtrees
Into Blocks (easy version)
Salazar Slytherin's Locket
Factorial modulo $p$
Hongcow Buys a Deck of Cards
Intersection Point of Lines
Linear Diophantine Equation
Zip-line
Exercising Walk
Invertation in Tournament
A Trivial Problem
Giải Thuật Và Lập Trình - Lê Minh Hoàng
Pavel and barbecue
Crazy Diamond
Barcode
PolandBall and Gifts
The Stern-Brocot tree and Farey sequences
Finding articulation points in a graph in $O(N+M)$
Một số vấn đề đáng chú ý trong môn Tin học - Phan Công Minh
String Set Queries
Cookie Clicker
Xenia and Colorful Gems
Boredom
Andrey and Problem
Range Minimum Query
Wrong Answer on Test 233 (Hard Version)
Rational Resistance
Dreamoon Likes Strings
Paint the Digits
A Lot of Games
Wonder Room
Bribes