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:
Finding common tangents to two circles
Professor GukiZ and Two Arrays
Finding Power of Factorial Divisor
Messy
Bear and Destroying Subtrees
Paint the String
Running with Obstacles
Football
Ancient Prophesy
Zuma
Wilbur and Points
Preorder Test
Nested Rubber Bands
Chicken or Fish?
Clockwork Bomb
Coffee Varieties (hard version)
Guess Your Way Out!
Mischievous Mess Makers
Group Projects
Correcting Mistakes
Slime and Biscuits
Sum of Nestings
Captain Marmot
Lowest Common Ancestor - Tarjan's off-line algorithm
Close Vertices
Cow and Treats
Chinese Remainder Theorem
Born This Way
Niyaz and Small Degrees
Dice Tower
Permutations
Euler's totient function