令 $k$ 为最小的 $i$ 满足 $X_i>X_{i+1}$。显然 $X_{k+1}$ 之后不会有未在 $X$ 中出现的数，否则可以将 $X_k$ 替换为 $X_{k+1}$ 使得字典序更小。同时 $X_{i-1}$ 和 $X_i$ 之间不可能有 $< X_i$ 的数。因此序列一定形如 $(>X_1),X_1,(>X_2),X_2,\ldots,(>X_k),X_k,(>X_k),X_{k+1},X_{k+2},\ldots, X_M$，且容易发现满足该条件的序列都是合法的。注意到从小到大加数时每个数可以放的位置个数是确定的，因此直接相乘即可。时间复杂度 $O(N)$。