牛牛的汉密尔顿路径

题号：NC21655
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

牛牛最近在学汉密尔顿路径，他碰到这样一个题

给你一副无向图n个点,标号为0到n-1, 每个点有一种颜色

你想要走遍图中的每一个点恰好一次，可以从任意位置开始走，以任意位置结束
假设走的序列是c1,c2,c3...,cn,如果ci cj的颜色相同，那么[ci, cj]之间的点的颜色都要是相同的颜色
请问有多少种不同的走法,模10⁹+7

第一行输入两个整数n,m （2≤ n ≤ 100, 1 ≤ m ≤ 2500）表示点数与边数

第二行输入n个整数表示每个点颜色color[i], (0 ≤ color[i] ≤ 9),每种颜色最多出现10次

第三行输入m个数表示每条边的起点

第四行输入m个数表示每条边的终点

输出一个整数

示例1

复制

9 12
0 0 0 1 1 1 2 2 2
0 1 2 3 4 5 6 7 8 0 3 6
1 2 0 4 5 3 7 8 6 3 6 0

复制

示例2

复制

9 12 
0 0 0 1 1 1 2 2 2
0 1 2 3 4 5 6 7 8 0 4 8
1 2 0 4 5 3 7 8 6 3 7 2

复制

子任务一30分：n<=20

子任务二30分：n<=50

子任务三40分：n<=100

子任务3依赖于子任务1，子任务2依赖于子任务1