题目描述

一年一度的村庄嘉年华开始了！小熊BIBO开心地在各个村庄里逛来逛去，她发现每个村庄都插了一面旗帜。嘉年华的组织者大熊告诉她，一共有T种纯色旗帜，每种旗帜的颜色都不一样，而为了热闹，相邻村庄不能插同一种颜色的旗帜。小熊BIBO很好奇，究竟有多少种插旗方案呢？

输入格式

输入的第一行，是3个数字$N,T$和$M$，表示一共有$N$个村庄，$T$种旗帜，以及$M$对相邻关系。

接下来的$M$行，每行有两个数字$x,y$，表示村庄$x$和$y$相邻。

输出格式

输出仅有一个数字，表示有多少种插旗方案。因为这个数字很大，所以你只需要输出它除以1117的余数就可以了。

样例输入输出

3 3 3 
1 2 
1 3 
2 3

6

说明/提示

30%的数据，保证$1<=n<=5;1<=t<=5$.

100%的数据，保证$1<=n<=8;1<=t<=20$.