题号：NC282541
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
时间限制：C/C++/Rust/Pascal 3秒，其他语言6秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld
题目描述
本题与 hard version 的区别在于每个颜色的随机区间是固定的，同时只有一组全局询问，相对的数据范围也有变化。
题目背景
正因为如此，他才没有察觉。
他没有察觉到，有个少女知晓一切——不，策划一切，并伸手打算为这场战斗画下真正的句点。
宫里学长抬起眼,察觉到有只手从眼角余光逼近，但迟了数秒才反应过来——这是他致命的失误。正欲转身闪躲的学长，惊愕地目睹桐香出人意料、快狠准的伸手动作。
桐香的指尖挖进宫里学长的太阳穴，勾起头带甩出去。白色的布条高高舞上日暮时分的紫红色天空，如垂死的鸟般挣扎片刻，最后终究失去力量，在尚未恢复流动的时间中随风飘落。
有人高高举起手，抓住那条白色尸骸。
——是会长。
题目描述
他没有察觉到，有个少女知晓一切——不，策划一切，并伸手打算为这场战斗画下真正的句点。
宫里学长抬起眼,察觉到有只手从眼角余光逼近，但迟了数秒才反应过来——这是他致命的失误。正欲转身闪躲的学长，惊愕地目睹桐香出人意料、快狠准的伸手动作。
桐香的指尖挖进宫里学长的太阳穴，勾起头带甩出去。白色的布条高高舞上日暮时分的紫红色天空，如垂死的鸟般挣扎片刻，最后终究失去力量，在尚未恢复流动的时间中随风飘落。
有人高高举起手，抓住那条白色尸骸。
——是会长。
题目描述
IT 社在运动会的夺棒中大获全败，伊藤在熬了三天三夜之后得出了一个伟大的模型！
已知我方有
个人，夺棒总共有 
个方面，其中各个人有各个擅长的方面，第 
个人擅长第 
个方面。
但是实际上只有一些位置我们已经确定好了人选，其 也是确定的，而有一些位置我们还没决定好会选谁，所以其 是在 ![[1,m]](https://www.nowcoder.com/equation?tex=%5B1%2Cm%5D)
中随机取的。
红方每次攻击都会先选择一个区间进行攻击。
伊藤这个伟大的模型断定，如果有两个人拥有同一种才能，那么这方面的才能就只能发挥一次，每次红方攻击的区间的牢固度，即为区间内不同才能的种数。
但是显然伊藤不知道红方的攻击策略，于是默认他们随机选择区间进行攻击。
作为 IT 社底层社员，你的任务是：对于上面发下来的预编排位置，计算红方攻击的区间的牢固度的期望值，并对
取模。
已知我方有
但是实际上只有一些位置我们已经确定好了人选，其
红方每次攻击都会先选择一个区间进行攻击。
伊藤这个伟大的模型断定，如果有两个人拥有同一种才能，那么这方面的才能就只能发挥一次，每次红方攻击的区间的牢固度，即为区间内不同才能的种数。
但是显然伊藤不知道红方的攻击策略，于是默认他们随机选择区间进行攻击。
作为 IT 社底层社员，你的任务是：对于上面发下来的预编排位置，计算红方攻击的区间的牢固度的期望值，并对
简要题意
给一个长度为 的序列，其中 要么是一个在 内的定值，要么是 
表示在 内的随机值，现在随机一个区间，问你区间期望颜色数量是多少，对 取模。
数据范围
输入描述:
第一行，两个整数和
，分别表示人数和方面数。
第二行，，表示每个人擅长哪方面，是
则随机。
输出描述:
第一行，一个整数，表示最后牢固度的期望值，对取模。