{"raw_statement":[{"iden":"statement","content":"He tells you that these trees are very peculiar. First, they are flat: one of their sides is facing south and the other is facing north. Second, when one of their branches splits, it splits in exactly two sub-branches, which go in two opposite directions: one goes towards the west and the other goes towards the east. All in all, such a tree can be very easily represented as a binary tree such as computer scientists are used to. (Mathematically, a binary tree is either the empty tree or an internal node with exactly two children, which are themselves binary trees.)\n\nAs a great programmer, you get excited as soon as you hear about binary trees. Darwin continues his explanations: in such a tree, branches are either horizontal or go up. Still obsessed by binary trees, you figure out that this corresponds to saying that, in the binary tree representation, if internal nodes are labelled by the elevation (distance from the ground) of the corresponding branch split, then the label of a non-root node is always larger than or equal to the label of its parent. Empty trees are not labelled.\n\nWhile you find this property rather boring and not very interesting, Darwin goes on and tells you a really astonishing and subtle fact he recently discovered about his favorite species of trees. After a lengthy discussion with Darwin, you finally understand that this property can be simply expressed in the binary tree representation. Namely, if one does an inorder traversal of the labeled binary tree of any tree of that species, the resulting sequence of elevations is always the same! (The inorder traversal of the empty tree is the empty sequence and, if a tree is not empty, its inorder traversal is the concatenation of the inorder traversal of the left sub-tree, followed by the label of the top node, followed by the inorder traversal of the right sub-tree.)\n\nAfter having heard the impressive research results of your friend, you urge him to elaborate on the methodology he uses to count the varieties of this particularly surprising species. This leads him to reveal the hypothesis he is currently working on: every tree of a given variety is represented by the same binary tree, which uniquely identifies that variety. Moreover, every labeled binary tree verifying the conditions above indeed corresponds to an existing variety. Darwin believes that some kind of mathematical tool could then be used to count the varieties, but he has not enough mathematical background to do so.\n\nNow that you are really impressed by Darwin's work, it is your turn: impress him by writing a program that counts the number of varieties of that species.\n\nThe input consists of the following lines: \n\nBoth $N$ and the elevations are greater than or equal to 0 and less than or equal to 1000000.\n\nA single line with a single integer, the number of varieties of trees in the species, modulo $1000000007$.\n\n"},{"iden":"input","content":"The input consists of the following lines:   on the first line: the number $N$ of elements of the sequence of elevations produced by the inorder traversal of any tree of the species;  the $N$ following lines represent the sequence of elevations, in millimeters, with one integer per line.  *Limits*Both $N$ and the elevations are greater than or equal to 0 and less than or equal to 1000000."},{"iden":"output","content":"A single line with a single integer, the number of varieties of trees in the species, modulo $1000000007$."},{"iden":"examples","content":"Input6\n3\n1\n6\n2\n4\n5\nOutput1\nInput6\n1\n1\n1\n1\n1\n1\nOutput132\n"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ G = (V, E) $ be an undirected multigraph with $ |V| = n $ vertices (islands) and $ |E| = b $ edges (bridges).  \nEach edge $ e_i \\in E $ has a culture value $ c_i \\in \\mathbb{Z}_{\\geq 0} $.  \nThe graph $ G $ is connected.\n\nLet $ \\mathcal{M} $ be the set of all spanning subgraphs of $ G $ that:  \n- Are connected,  \n- Maximize the number of edges removed (i.e., minimize the number of edges retained),  \n- Among all such minimal connected subgraphs, maximize the total culture value.\n\nLet $ m = \\max \\left\\{ \\sum_{e \\in F} c_e \\mid F \\subseteq E,\\ (V, F) \\text{ is connected},\\ |F| = \\min\\{|F'| : (V, F') \\text{ connected}\\} \\right\\} $.\n\nLet $ \\mathcal{F}^* $ be the set of all edge sets $ F \\subseteq E $ such that $ (V, F) $ is connected, $ |F| = n - 1 $, and $ \\sum_{e \\in F} c_e = m $.  \n(Note: $ |F| = n - 1 $ since the minimal connected subgraph is a spanning tree.)\n\nFor each query $ i $, given a set $ S_i \\subseteq E $ of bridges, define:  \n$$\n\\text{Answer}_i = \\max \\left\\{ |F \\cap S_i| \\mid F \\in \\mathcal{F}^* \\right\\}\n$$\n\n**Constraints**  \n1. $ 1 \\le t \\le 616 $  \n2. $ 1 \\le n \\le 66666 $, $ 1 \\le b \\le 133332 $, sum of $ n $ over test cases $ \\le 66666 $, sum of $ b $ over test cases $ \\le 133332 $  \n3. $ q \\ge 1 $, each $ S_i \\subseteq E $, $ |S_i| \\ge 1 $, all elements in $ S_i $ distinct  \n4. Sum of $ |S_i| $ over all queries in a test case $ \\le b $  \n5. $ 0 \\le c_i \\le 133332 $, $ 1 \\le x_i, y_i \\le n $  \n6. $ G $ is connected  \n\n**Objective**  \nFor each test case:  \n- Compute $ m $: the maximum total culture among all spanning trees of $ G $.  \n- For each query $ S_i $, compute the maximum number of bridges from $ S_i $ that can be included in a spanning tree achieving total culture $ m $.","simple_statement":"You are given a connected graph with n islands and b bridges. Each bridge has a culture value. You must remove as many bridges as possible while keeping the graph connected — this is called a \"max destruction\". Among all such max destructions, find the one with the maximum total culture of remaining bridges. Call this maximum total culture m.\n\nNow, for q queries, each gives a set S of bridges. For each query, what is the maximum number of bridges from S that can be kept, while still:\n- keeping the graph connected,\n- removing the maximum number of bridges possible (i.e., using a max destruction),\n- and keeping the total culture exactly m?\n\nAnswer each query with that maximum number.","has_page_source":false}