{"trustable":false,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003e \u003cspan\u003e你在纸上画了一棵有根树,这棵树有\u003c/span\u003e\u003cspan\u003en\u003c/span\u003e\u003cspan\u003e个点,保证树的根编号为\u003c/span\u003e\u003cspan\u003e1.\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003e一开始每个节点上面的值都为\u003c/span\u003e\u003cspan\u003e0\u003c/span\u003e\u003cspan\u003e。现在有\u003c/span\u003e\u003cspan\u003eq\u003c/span\u003e\u003cspan\u003e个询问,每个询问有两种类型:\u003c/span\u003e\u003c/p\u003e \n\u003col type\u003d\"1\"\u003e \n \u003cli\u003e \u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e格式:\u003c/span\u003e\u003cspan\u003e1\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003cspan\u003e v x k \u003c/span\u003e\u003cspan\u003e。\u003c/span\u003e\u003cspan\u003e \u003c/span\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e你需要给\u003c/span\u003e\u003cspan\u003ev\u003c/span\u003e\u003cspan\u003e节点的值增加\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003cspan\u003e \u003c/span\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003ex\u003c/span\u003e\u003cspan\u003e,给\u003c/span\u003e\u003cspan\u003ev\u003c/span\u003e\u003cspan\u003e节点的儿子的值增加\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003cspan\u003e x - k\u003c/span\u003e\u003cspan\u003e,等等。如果\u003c/span\u003e\u003cspan\u003ev\u003c/span\u003e\u003cspan\u003e的子孙\u003c/span\u003e\u003cspan\u003eu\u003c/span\u003e\u003cspan\u003e,与\u003c/span\u003e\u003cspan\u003ev\u003c/span\u003e\u003cspan\u003e的距离为\u003c/span\u003e\u003cspan\u003ei\u003c/span\u003e\u003cspan\u003e,那么需要给节点\u003c/span\u003e\u003cspan\u003eu\u003c/span\u003e\u003cspan\u003e上的值增加\u003c/span\u003e\u003cspan\u003e (x - i * k)\u003c/span\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e。两个点间的距离定义为两点之间的最短路。\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \n \u003cli\u003e \u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e格式:\u003c/span\u003e\u003cspan\u003e2\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003cspan\u003e v\u003c/span\u003e\u003cspan\u003e \u003c/span\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e。你想要输出节点\u003c/span\u003e\u003cspan\u003ev\u003c/span\u003e\u003cspan\u003e上的值。\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/li\u003e \n\u003c/ol\u003e \n\u003cp\u003e 给出这棵树和所有的询问,对于每个第二种类型的询问,你需要输出相应的值 mod \u003cspan\u003e\u003cspan\u003e\u003cspan\u003e1000000007。\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e \u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e第一行包含一个整数\u003c/span\u003e\u003cspan\u003en\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003cspan\u003e\u0026nbsp;(\u003c/span\u003e\u003cspan\u003e1\u003c/span\u003e\u003cspan\u003e \u003c/span\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e≤\u003c/span\u003e\u003cspan\u003en\u003c/span\u003e\u003cspan\u003e≤\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003cspan\u003e \u003c/span\u003e300000\u003cspan\u003e)\u003c/span\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e,\u003c/span\u003e\u003cspan\u003e代表树的节点。\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e第二行有\u003c/span\u003e\u003cspan\u003en-1\u003c/span\u003e\u003cspan\u003e个整数\u003c/span\u003e\u003cspan\u003ep\u003c/span\u003e\u003cspan\u003e2\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003cspan\u003e,\u003c/span\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003ep\u003c/span\u003e\u003cspan\u003e3\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003cspan\u003e,\u003c/span\u003e\u003cspan\u003e \u003c/span\u003e\u003cspan\u003e...\u0026nbsp;\u003c/span\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003ep\u003c/span\u003e\u003cspan\u003en\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003cspan\u003e\u0026nbsp;(\u003c/span\u003e\u003cspan\u003e1\u003c/span\u003e\u003cspan\u003e \u003c/span\u003e\u003cspan\u003e\u003cspan\u003e≤\u003c/span\u003e\u003cspan\u003ep\u003c/span\u003e\u003cspan\u003ei\u003c/span\u003e\u003c/span\u003e\u003cspan\u003e\u0026lt;\u003c/span\u003e\u003cspan\u003ei\u003c/span\u003e\u003cspan\u003e)\u003c/span\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e,\u003c/span\u003e\u003cspan\u003epi\u003c/span\u003e\u003cspan\u003e表示第\u003c/span\u003e\u003cspan\u003ei\u003c/span\u003e\u003cspan\u003e个节点的父亲的编号。\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/p\u003e \n\u003cp\u003e \u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e第三行包含一个整数\u003c/span\u003e\u003cspan\u003eq\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003cspan\u003e(\u003c/span\u003e\u003cspan\u003e1\u003c/span\u003e\u003cspan\u003e \u003c/span\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e≤\u003c/span\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003eq\u003c/span\u003e\u003cspan\u003e≤\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003cspan\u003e 3\u003c/span\u003e\u003cspan\u003e00000\u003c/span\u003e\u003cspan\u003e)\u003c/span\u003e\u003cspan\u003e,代表询问的个数,接下来有\u003c/span\u003e\u003cspan\u003eq\u003c/span\u003e\u003cspan\u003e行询问,格式如上描述所说。\u003c/span\u003e\u003cspan\u003e(\u003c/span\u003e\u003cspan\u003ev\u003c/span\u003e\u003cspan\u003e,\u003c/span\u003e\u003cspan\u003ex\u003c/span\u003e\u003cspan\u003e,\u003c/span\u003e\u003cspan\u003ek\u003c/span\u003e\u003cspan\u003e\u0026nbsp;(\u003c/span\u003e\u003cspan\u003e1\u003c/span\u003e\u003cspan\u003e \u003c/span\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e≤\u003c/span\u003e\u003cspan\u003ev\u003c/span\u003e\u003cspan\u003e≤\u003c/span\u003e\u003cspan\u003en\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003cspan\u003e;\u003c/span\u003e\u003cspan\u003e\u0026nbsp;\u003c/span\u003e\u003cspan\u003e0\u003c/span\u003e\u003cspan\u003e \u003c/span\u003e\u003cspan\u003e\u003cspan\u003e≤\u003c/span\u003e\u003cspan\u003ex\u003c/span\u003e\u003c/span\u003e\u003cspan\u003e\u0026lt;\u003c/span\u003e\u003cspan\u003e1000000007\u003c/span\u003e\u003cspan\u003e;\u003c/span\u003e\u003cspan\u003e\u0026nbsp;\u003c/span\u003e\u003cspan\u003e0\u003c/span\u003e\u003cspan\u003e \u003c/span\u003e\u003cspan\u003e≤\u003c/span\u003e\u003cspan\u003ek\u003c/span\u003e\u003cspan\u003e\u0026lt;\u003c/span\u003e\u003cspan\u003e1000000007\u003c/span\u003e\u003cspan\u003e)\u003c/span\u003e\u003cspan\u003e)\u003c/span\u003e\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e \u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e对于每一个第二种询问,\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003cspan\u003e \u003c/span\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e输出相应的答案(\u003c/span\u003e\u003cspan\u003emod\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003cspan\u003e\u0026nbsp;\u003c/span\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e1000000007\u003c/span\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e\u003cspan\u003e)。\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/span\u003e\u003c/p\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cdiv\u003e \n \u003cdiv\u003e\n 3\n \u003c/div\u003e \n \u003cdiv\u003e\n 1 1\n \u003c/div\u003e \n \u003cdiv\u003e\n 3\n \u003c/div\u003e \n \u003cdiv\u003e\n 1 1 2 1\n \u003c/div\u003e \n \u003cdiv\u003e\n 2 1\n \u003c/div\u003e \n \u003cdiv\u003e\n 2 2\n \u003c/div\u003e \n\u003c/div\u003e \n\u003cdiv\u003e \n \u003cpre\u003e\r\n\t\u003c/pre\u003e \n\u003c/div\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cp\u003e 2\u003c/p\u003e \n\u003cp\u003e 1\u003c/p\u003e"}}]}