#P17944. Hiking Trip
Hiking Trip
Hiking Trip
从西到东有 处景点,高度依次为 。选择一个区间 徒步,满足以下条件时称该区间合法:
- 不存在 使 ,即内部没有严格山谷;
- 对所有 ,都有 ,即相邻景点不等高。
有些高度已知。每个未知高度分别独立、均匀地从 中的整数选取。求合法区间数量的期望,对 取模。
输入格式
第一行是测试用例数 ,。
每组用例第一行包含 。第二行包含 个整数 : 表示未知,否则表示确定的高度。
- ,所有用例的 ;
- ;
- 或 。
输出格式
每组用例输出一个整数,表示期望对 取模的结果。分数按分母的模逆元解释。
单点区间总是合法;严格上升、严格下降以及先严格上升后严格下降的区间都可能合法。
样例 1
10
4 4
1 4 2 3
3 3
-1 2 -1
4 2
-1 -1 -1 1
4 3
1 -1 -1 3
5 5
-1 2 -1 4 -1
6 4
2 -1 1 -1 -1 1
5 5
1 -1 4 -1 1
8 4
-1 2 -1 -1 2 -1 4 -1
9 7
4 -1 2 -1 -1 6 -1 4 -1
20 20
-1 -1 -1 5 -1 -1 13 -1 10 -1 -1 -1 -1 12 -1 3 -1 -1 -1 18
8
666666676
875000012
555555566
872000016
750000017
400000014
554687520
973046972
216066617