IOIC 王國是一個獨裁的國家，由帥哥總召 Robert 統治，這個國家一共有 $N$ 座城市以及 $M$ 條道路，每一條道路連接著兩座不同的城市。帥哥總召 Robert 為了監控整個王國，研發了 $K$ 種不同類型的機器人 (每個種類都有無數多個機器人)。他想要將機器人分配到每一條道路上，讓每一條道路都恰有一個機器人監控。

為了增加管理王國的趣味性，總召會進行一些操作，操作的方式如下：總召每次可以選擇一些不同的城市，編號分別為 $x_1, x_2, \ldots, x_t$，使得對所有 $1 \leq i \leq t$，編號 $x_i$ 與 $x_{i + 1}$ 的城市之間都有道路連接，其中 $x_{t + 1} = x_1$。接著，總召會旋轉這些道路上的機器人，也就是說在編號 $x_i$ 與 $x_{i + 1}$ 的城市之間的機器人，會移動到連接著編號 $x_{i + 1}$ 與 $x_{i + 2}$ 的城市之間的道路。

總召很好奇，在這樣的情況下，最多可以選出幾種不同的分配方式，使得對於任意兩種分配方式，都沒有辦法經過若干次操作從一種分配方式變成另一種分配方式？如果存在一條道路在兩種分配方式中被賦予不同種類的機器人，我們就說這兩種分配方式是不同的。