← 返回题目

题库练习「SCOI2016」萌萌哒

← 上一题下一题 →

A6878 | $「SCOI2016」萌萌哒$

来源省选

时间限制1s

内存限制256MB

通过 / 提交0/0

题目描述

一个长度为 $ n $ 的大数，用 $ S_1S_2S_3 \ldots S_n $表示，其中 $ S_i $ 表示数的第 $ i $ 位，$ S_1 $ 是数的最高位，告诉你一些限制条件，每个条件表示为四个数 $ (l_1, r_1, l_2, r_2) $，即两个长度相同的区间，表示子串 $ S_{l_1}S_{l_1 + 1}S_{l_1 + 2} \ldots S_{r_1} $ 与 $ S_{l_2}S_{l_2 + 1}S_{l_2 + 2} \ldots S_{r_2} $ 完全相同。 比如 $ n = 6 $ 时，某限制条件 $ (l_1 = 1, r_1 = 3, l_2 = 4, r_2 = 6) $，那么 $ 123123 $、$ 351351 $ 均满足条件，但是 $ 12012 $、$ 131141 $ 不满足条件，前者数的长度不为 $ 6 $，后者第二位与第五位不同。问满足以上所有条件的数有多少个。

输入格式

第一行两个数 $ n $ 和 $ m $，分别表示大数的长度，以及限制条件的个数。 接下来 $ m $行，对于第 $ i $ 行，有 $ 4 $ 个数 $ {l_i}_1 $、$ {r_i}_1 $、$ {l_i}_2 $、$ {r_i}_2 $，分别表示该限制条件对应的两个区间。

输出格式

一个数，表示满足所有条件且长度为 $ n $ 的大数的个数，答案可能很大，因此输出答案模 $ 10 ^ 9 + 7 $ 的结果即可。

输入输出样例

输入 #1

4 2
1 2 3 4
3 3 3 3

输出 #1

C++ 编辑器

输入

输出