Original proposer: physics0523

It is meaningless to flip the same card three or more times. (We only need to flip a card once to know what integer is written, and once to eat it.)
This means the answer is \(0\) for \(M > 2N\).
Furthermore, your actions can be constrained into the following two types:

• Flip the card that you already know has \(x\) written on it, and eat it.
• Choose any one card whose number written in the front you do not know.

Thus, your strategy should be:

• If you know the card with \(x\) written on it, choose it.
  • Compared to choosing an unknown card although you know the card with \(x\), choosing the known \(x\) and eating it is never worse.
• Otherwise, choose any one unknown card.

The number of operations equals \(N\) plus the number of times you flipped the card but it was not the immediately eatable card.
Now, in what situation do we flip an unknown card?
When the immediately eatable card is contained in the unknown cards, you always choose an unknown card; otherwise, you should always choose the known immediately-eatable card and eat it. More precisely, when there are \(k\) unknown cards, you can immediately eat the card with the probability of \(1/k\) regardless of the numbers written on the known cards.
Moreover, as long as you follow the strategy above, there is exactly one state where there are exactly \(i\) unknown cards, for all \(i\) (\(1 \le i \le N\)).
Hence, the solution is the coefficient of \(x^{M-N}\) in the following polynomial:

• \(\displaystyle \prod_{k=1}^{N} \left ( \frac{k-1}{k}x + \frac{1}{k} \right ).\)

The perspective becomes clearer by multiplying the \(k\)-th term by \(k\), and globally dividing by \(N!\), to make all coefficients integer except for the global factor.

All that left is to find the total product of the \(N\) degree-\(1\) polynomials.
This can be done by convolving them in the form of a binary tree with \(O(\log N)\) layers. Each layer costs \(O(N \log N)\), so the total cost is \(O(N \log^2 N)\). (In the implementation, put the polynomials in a queue, and repeatedly take the first two elements, convolve it, and push it to the tail.)

The time complexity of this solution is \(O(N \log^2 N)\).

Note that the answers multiplied by \(N!\) constitute Stirling numbers of the first kind, so it may be possible to experimentally derive this fact and find the answer.

Sample code (C++):

#include<bits/stdc++.h>
#include<atcoder/all>

using namespace std;
using namespace atcoder;

using mint=modint998244353;

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n,m;
  cin >> n >> m;
  if(m>2*n){cout << "0\n"; return 0;}
  queue<vector<mint>> q;
  for(int k=1;k<=n;k++){
    q.push({1,(mint)(k-1)});
  }
  while(q.size()>=2){
    auto l=q.front(); q.pop();
    auto r=q.front(); q.pop();
    q.push(convolution(l,r));
  }
  mint div=1;
  for(int i=2;i<=n;i++){
    div*=((mint)i);
  }
  auto f=q.front(); q.pop();
  cout << (f[m-n]/div).val() << "\n";
  return 0;
}