一年一度的村庄嘉年华开始了！小熊BIBO开心地在各个村庄里逛来逛去，她发现每个村庄都插了一面旗帜。嘉年华的组织者大熊告诉她，一共有T种纯色旗帜，每种旗帜的颜色都不一样，而为了热闹，相邻村庄不能插同一种颜色的旗帜。小熊BIBO很好奇，究竟有多少种插旗方案呢？
输入的第一行，是3个数字N，T和M，表示一共有N个村庄，T种旗帜，以及M对相邻关系。
接下来的M行，每行有两个数字x，y，表示村庄x和y相邻。
30%的数据，保证1<=n<=5;1<=t<=5.
70%的数据，保证1<=n<=7;1<=t<=20.
100%的数据，保证1<=n<=8;1<=t<=20.
输出仅有一个数字，表示有多少种插旗方案。因为这个数字很大，所以你只需要输出它除以1117的余数就可以了。
3 3 3 1 2 1 3 2 3
6