CodeForces - 1312D Count the Arrays（思维+组合数学）

D -Count the Arrays

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 aj<aj+1, if j<i, and aj>aj+1, if j≥i).

Input

The first line contains two integers n and m (2≤n≤m≤2⋅105).

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].

题意：

给定n,m，让你构造一个长度为n的数组，要求这n个数都必须在1~m范围内，且要有两个数相同，数组内的值是先上升再下降的形式，问能够构造的组数。

思路：

昨晚做完C就到时间了，今早一看其实挺好想的。

很容易想到我们选择一个最大值放在倒数第二位，因为要保证了先上升再下降的形式，所以最大值必然只有一个。

我们可以先从m个数里选择n-1个数，这其中包括最大值。再从剩下的n-2个数里选择一个放在最后一位。

再来考虑一下这一组数内部的顺序问题，最大值的位置是不会变的，两个相等的数位置变了也没有影响，剩下的n-3个数，有最大值左边和最大值右边两种情况，所以是2^（n-3）。

被内部的顺序问题卡住了qwq

组合数学模板：传送门

代码：

要注意特判n==2的情况，不然用lucas会t

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll m,n,p=998244353;
ll ksm(ll a,ll b,ll p){
  ll res=1;
  while(b){
//&运算当相应位上的数都是1时，该位取1，否则该为0。
    if(b&1)
      res=1ll*res*a%p;//转换为ll型
    a=1ll*a*a%p;
    b>>=1;//十进制下每除10整数位就退一位 
  }
  return res;
}
ll c(ll a,ll b,ll p){
  if(b>a) return 0;
  ll res=1; 
  for(int i=1,j=a;i<=b;i++,j--){
    res=res*j%p;
    res=res*ksm(i,p-2,p)%p;//逆元 
  }
  return res; 
}
ll lucas(ll a,ll b,ll p){
  if(a<p &&b<p) return c(a,b,p);
  return c(a%p,b%p,p)*lucas(a/p,b/p,p)%p;
}
int main(){
    cin>>n>>m;
    if(n==2){
        puts("0");
        return 0;
    }
    ll res=lucas(m,n-1,p)%p*ksm(2,n-3,p)%p*(n-2)%p;
    cout<<res;
  return 0;
}