#P7988. Pty loves SegmentTree
Pty loves SegmentTree
Pty loves SegmentTree
题目描述
Consider rooted interval trees. A node represents an interval . If , it is a leaf; otherwise choose any integer , with left child and right child .
Assign weight 1 to each leaf. An internal node has weight if its right child's interval contains exactly integers, and weight otherwise. The weight of a tree is the product of all its node weights.
Let be the sum of the weights of all such trees rooted at . Different ordered tree shapes count separately.
For each query , compute
输入格式
The first line contains ().
For each case, the first line contains , where , , and .
The next lines each contain ().
输出格式
For each query, print the answer on one line.
样例输入1
1
1 1 3 1
4 4
样例输出1
3249
样例说明
For , the five ordered shapes have weights . Thus , and the answer is .