在電影《超能陸戰(zhàn)隊》中，小宏可以使用他的微型機器人組合成各種各樣的形狀。
現(xiàn)在他用他的微型機器人拼成了一個大玩具給小朋友們玩。為了更加美觀，他決定給玩具染色。

小宏的玩具由n個球型的端點和m段連接這些端點之間的邊組成。下圖給出了一個由5個球型端點和4條邊組成的玩具，看上去很像一個分子的球棍模型。
 
由于小宏的微型機器人很靈活，這些球型端點可以在空間中任意移動，同時連接相鄰兩個球型端點的邊可以任意的伸縮，這樣一個玩具可以變換出不同的形狀。在變換的過程中，邊不會增加，也不會減少。

小宏想給他的玩具染上不超過k種顏色，這樣玩具看上去會不一樣。如果通過變換可以使得玩具變成完全相同的顏色模式，則認為是本質(zhì)相同的染色?，F(xiàn)在小宏想知道，可能有多少種本質(zhì)不同的染色。

輸入的第一行包含三個整數(shù)n, m, k，
分別表示小宏的玩具上的端點數(shù)、邊數(shù)和小宏可能使用的顏色數(shù)。端點從1到n編號。
接下來m行每行兩個整數(shù)a, b，表示第a個端點和第b個端點之間有一條邊。輸入保證不會出現(xiàn)兩條相同的邊。

輸出一行，表示本質(zhì)不同的染色的方案數(shù)。由于方案數(shù)可能很多，請輸入方案數(shù)除10007的余數(shù)。

零基礎同學可以先學習視頻課程，包含C/C++、Python、百練、藍橋杯輔導、算法數(shù)據(jù)結(jié)構(gòu)等課程，提供視頻講解以及配套習題，還有老師答疑，點擊這里了解課程詳情

藍橋杯