小 Y 最近学会了如何用线段树维护序列,并支持区间求和的操作。
以下给出本题中线段树的定义。 该定义可能和你熟知的线段树有区别。
- 线段树是一种有根的二叉树,其每个节点对应了序列上的一个区间
,其中根节点对应 。 - 对于每个节点,若其代表的序列区间
满足 ,则其为叶节点;否则存在整数 ,满足其左儿子代表区间 ,右儿子代表区间 。 - 线段树的形态取决于每个非叶结点的划分点
的选择。 - 在区间求和的问题上,对于序列
,线段树的每个结点 维护了 的值。
小 J 有一个长度为
例如,如果
小 J 有
- 如果已知
中所有结点维护的值,则每个 区间的和都能被唯一确定。
例如,如果已知
由于答案很大,你需要输出答案对
输入格式
输入的第一行包含两个整数
输入的第二行包含
接下来
输出格式
输出一行一个整数表示答案对
样例 #1
样例输入 #1
2 1 1 0 2
样例输出 #1
5
样例 #2
样例输入 #2
2 1 1 1 2
样例输出 #2
5
样例 #3
样例输入 #3
5 2 2 1 4 3 1 3 2 5
样例输出 #3
193
样例 #4
样例输入 #4
10 10 5 2 1 3 4 7 6 8 9 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10
样例输出 #4
70848
提示
样例 1 解释
只有当直接知道
数据范围
对于所有测试数据:
, , ,- 保证
正确描述了一棵线段树, , 。
子任务 1(6 分):
子任务 2(18 分):
子任务 3(9 分):
子任务 4(17 分):
子任务 5(10 分):
子任务 6(13 分):
子任务 7(7 分):
子任务 8(20 分):无额外限制。
时间限制:
空间限制: