題目描述

有一個由 𝑁 個數字組成的數列, 這數列是 1 至 𝑁 的某種排列。這個數列經過 𝐾 輪操作後, 變成了一個由 1 至 𝑁 的順序排列。而每輪操作都是相同的, 在每一輪操作都有 𝑃 個指令, 每個指令是將指定的位置上的數字對換。我們想知道在未進行任何操作前, 最初的數列是什麼?

由於數列可能很長，所以我們不需要輸出整個數列，只需要輸出三個代表性的整數就可以，它們分別為 𝐴, 𝐵, 𝑆。

𝐴 是最初數列中的第一個數
𝐵 是最初數列中的最後一個數
𝑆 是最初數列中的測和，其計算方法如下：設最初數列為 𝑑₁, 𝑑₂, 𝑑₃, ... , 𝑑_𝑁, 則其測和為
𝑆 = ( 𝑑₁ × 𝑁⁰ + 𝑑₂ × 𝑁¹ + 𝑑₃ × 𝑁² + ... + 𝑑_𝑁 × 𝑁^{𝑁 − 1} ) mod 1000000007

其中， mod 1000000007 為取餘運算（即除以1000000007 後取其餘數）。

輸入格式

輸入第一行有三個正整數, 分別為 𝑁 𝐾 𝑃 (其代表意義見上文內容)

隨後有 𝑃 行, 每行有兩個正整數 𝑎 及 𝑏, 代表要將位置在 𝑎 及 𝑏 上的兩個數字對調 (1 ≤ 𝑎, 𝑏 ≤ 𝑁)

輸出一行, 其上有 3 個數字 𝐴 𝐵 𝑆, 每個數字之間以一個空格分開。這個數字為最初數列的代表性數字，其定義見上面題目的描述。

3 2 199

10 ≤ 𝑁 ≤ 100000, 𝑁 ≤ 𝐾 ≤ 2𝑁,𝑁/2≤ 𝑃 ≤ 2𝑁
對於30%的數據， 𝑁 ≤ 1000
對於70%的數據，𝑁 ≤ 10000

最初排列: 3 1 4 2 (這是最初的數列，因為它經過下面題目要求的操作後，會變為 1 至 4 的順序排列）
第一輪操作後: 4 3 2 1
第二輪操作後: 2 4 1 3
第三輪操作後: 1 2 3 4 (得到 1 至 4 的順序排列)

因此，輸出為數列的第一個數（即 3）, 最後一個數（即 2），及它們的測和： (3 ×40 + 1 ×41 + 4 ×42 + 2 ×43 ) mod 1000000007 = 199