a122. TOI 2025/06 潛力組：排列順序

題目描述

從整數 1 到 M 中取出 N 個互不相同的數字，依序組成長度 N 的數列。將所有可能的數列按字典序排序，從 0 開始編號。字典序比較時，第一個不同位置的數字較小者排在前面。

給定其中一個數列，請計算它的編號對 1000000007 取餘數的結果。

輸入格式

第一行為 N、M；第二行為 N 個數字 aᵢ。

• 1 ≤ N ≤ M ≤ 200000
• 1 ≤ aᵢ ≤ M，且所有 aᵢ 互不相同。

輸出格式

輸出數列的零起算字典序編號除以 1000000007 的餘數。

來源

TOI 2025 年 6 月潛力組〈排列順序〉。本敘述重新撰寫；範例與測資為另行設計。 https://tpmso.k12ea.gov.tw/toi/wp-content/uploads/question/202506/Permutation.pdf