题目背景

城市规划师林澈正在整理一座老城区的道路档案。城区中的每个路口都有编号，道路均为双向道路。由于历史建设方式特殊，这张路网中虽然存在一些环形街区，但任意一个路口最多只会属于一个环形街区。

档案馆准备重新编号所有路口。若重新编号前后，任意两个编号之间是否有道路连接都完全一致，那么这次重新编号不会改变路网的结构。林澈希望知道，一共有多少种这样的重新编号方案。

题目描述

一个顶点仙人掌图是满足以下条件的无向连通图：

• 图是连通的；
• 每个顶点至多属于一个简单环。

简单环指不重复经过任何顶点的环。

下面是一张顶点仙人掌图的示意图：

给定一个包含 $n$ 个顶点的顶点仙人掌图，顶点编号为 $1,2,\ldots,n$。

该图的一个自同构是一个排列

$$p_1,p_2,\ldots,p_n,$$

满足：对于任意两个顶点 $i,j$，原图中存在边 $i-j$，当且仅当原图中存在边 $p_i-p_j$。

换言之，把每个顶点 $i$ 重新编号为 $p_i$ 后，图的邻接关系保持不变。

请计算该图的自同构数量，并对 $10^9+3$ 取模。

输入格式

第一行包含两个整数 $n,m$，分别表示顶点数和边数。

接下来 $m$ 行，每行包含两个整数 $u,v$，表示顶点 $u$ 与顶点 $v$ 之间存在一条无向边。

输出格式

输出一个整数，表示该图的自同构数量对 $10^9+3$ 取模后的结果。

数据范围与保证

• $1\le n\le 200$；
• $0 \le m \le n-1+\left\lfloor\dfrac{n}{3}\right\rfloor$；
• $1 \le u,v \le n$，且 $u \ne v$；
• 任意两个顶点之间至多存在一条边；
• 输入图保证连通；
• 每个顶点至多属于一个简单环。

样例 1

输入

4 3
1 2
1 3
1 4

输出

6

说明

顶点 $2,3,4$ 可以任意排列，共有 $3!=6$ 种方案。

样例 2

输入

4 4
1 2
2 3
3 4
4 1

输出

8

说明

四个顶点构成一个环。可以进行任意循环位移，也可以翻转整个环，因此共有 $4 \times 2=8$ 种方案。

样例 3

输入

6 7
1 2
2 3
3 1
4 5
5 6
6 4
1 4

输出

8

说明

两个三角形可以互换；在每个三角形内部，还可以交换两个不与另一个三角形相连的顶点，因此共有 $2 \times 2 \times 2=8$ 种方案。

样例 4

输入

18 21
1 2
2 3
3 4
2 4
1 5
1 10
5 10
5 6
6 7
7 8
7 16
7 17
7 9
6 9
10 18
18 12
12 11
11 18
12 13
12 14
12 15

输出

144

说明

该数据对应题目描述中的示意图。

样例 5

输入

1 0

输出

1

说明

只有一个顶点时，仅有恒等排列。

样例 6

输入

200 224
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 2
1 12
12 13
13 14
14 15
15 16
16 17
17 18
18 19
19 20
20 21
21 12
1 22
22 23
23 24
24 25
25 26
26 27
27 28
28 29
29 30
30 31
31 22
1 32
32 33
32 34
34 35
35 36
36 32
1 37
37 38
37 39
39 40
40 41
41 37
1 42
42 43
42 44
44 45
45 46
46 42
1 47
47 48
47 49
49 50
50 51
51 47
1 52
52 53
52 54
54 55
55 56
56 52
1 57
57 58
57 59
59 60
60 61
61 57
1 62
62 63
62 64
64 65
65 66
66 62
1 67
67 68
67 69
69 70
70 71
71 67
1 72
72 73
72 74
74 75
75 76
76 72
1 77
77 78
78 79
79 80
80 81
81 77
1 82
82 83
83 84
84 85
85 86
86 82
1 87
87 88
88 89
89 90
90 91
91 87
1 92
92 93
93 94
94 95
95 96
96 92
1 97
97 98
98 99
99 100
100 101
101 97
1 102
102 103
103 104
104 105
105 106
106 102
1 107
107 108
108 109
109 110
110 111
111 107
1 112
112 113
113 114
114 115
115 116
116 112
1 117
117 118
118 119
119 120
120 121
121 117
1 122
122 123
123 124
124 125
125 126
126 122
1 127
127 128
128 129
129 130
130 131
131 127
1 132
132 133
133 134
134 135
135 136
136 132
1 137
137 138
138 139
139 140
140 141
141 137
1 142
142 143
142 144
142 145
1 146
146 147
146 148
146 149
1 150
150 151
150 152
150 153
1 154
154 155
154 156
154 157
1 158
158 159
158 160
158 161
1 162
162 163
162 164
162 165
1 166
166 167
167 168
166 169
166 170
166 171
166 172
1 173
173 174
174 175
173 176
173 177
173 178
173 179
1 180
180 181
181 182
180 183
180 184
180 185
180 186
1 187
187 188
188 189
187 190
187 191
187 192
187 193
1 194
194 195
195 196
194 197
194 198
194 199
194 200

输出

886565533

说明

该样例用于展示答案需要对 $10^9+3$ 取模。