solutions: ["(n, q) = map(int, input().split())\nmod = 1000000007\nans = (pow(2, n + 1, mod) - 2) % mod\ntop = 1\nbottom = pow(2, n, mod)\nfor i in range(q):\n\tx = input()\n\tif x == '2':\n\t\tprint(ans)\n\telse:\n\t\tx = x.split()\n\t\tx = int(x[1])\n\t\tif x == 1 or x == 2:\n\t\t\tans = (2 * ans + n + 1) % mod\n\t\t\ttop = 2 * top % mod\n\t\t\tbottom = 2 * bottom % mod\n\t\telif x == 3:\n\t\t\tans = (2 * ans + top) % mod\n\t\t\ttop = bottom\n\t\t\tn = (2 * n + 1) % mod\n\t\telse:\n\t\t\tans = (2 * ans + bottom) % mod\n\t\t\tbottom = top\n\t\t\tn = (2 * n + 1) % mod\n", "import sys\nfrom itertools import *\n\ndef numIN(x=' '):\n\treturn map(int, sys.stdin.readline().strip().split(x))\n(n, q) = numIN()\nans = 2 ** (n + 1) - 2\nl = r = n + 1\nb = 2 ** n\nu = 1\nfor _ in range(q):\n\tx = list(numIN())\n\tif x[0] == 2:\n\t\tprint(ans % 1000000007)\n\telif x[1] == 1:\n\t\tans *= 2\n\t\tans += r\n\t\tb *= 2\n\t\tu *= 2\n\telif x[1] == 2:\n\t\tans *= 2\n\t\tans += l\n\t\tb *= 2\n\t\tu *= 2\n\telif x[1] == 3:\n\t\tans *= 2\n\t\tans += u\n\t\tl *= 2\n\t\tr *= 2\n\t\tu = b\n\telse:\n\t\tans *= 2\n\t\tans += b\n\t\tl *= 2\n\t\tr *= 2\n\t\tb = u\n", "(n, q) = list(map(int, input().split()))\n(b, e) = (2 ** n, 2 ** (n + 1) - 2)\nc = 1\nn += 1\nfor _ in range(q):\n\tl = input().split()\n\tif l[0] == '1':\n\t\tx = l[1]\n\t\tif x == '1' or x == '2':\n\t\t\te = e * 2 + n\n\t\t\tb *= 2\n\t\t\tc *= 2\n\t\tif x == '3':\n\t\t\te = e * 2 + c\n\t\t\tc = b\n\t\t\tn *= 2\n\t\tif x == '4':\n\t\t\te = e * 2 + b\n\t\t\tb = c\n\t\t\tn *= 2\n\telse:\n\t\tprint(e % 1000000007)\n", "mod = 10 ** 9 + 7\n(n, q) = map(int, input().split())\ntop = 1\nbottom = 2 ** n % mod\nleft = (n + 1) % mod\nright = (n + 1) % mod\nedges = (2 ** n - 1) * 2 % mod\nfor _ in range(q):\n\ts = input()\n\tif int(s[0]) == 1:\n\t\tif int(s[2]) == 1:\n\t\t\tedges = (2 * edges % mod + right) % mod\n\t\t\ttop = top * 2 % mod\n\t\t\tbottom = bottom * 2 % mod\n\t\telif int(s[2]) == 2:\n\t\t\tedges = (2 * edges % mod + left) % mod\n\t\t\ttop = top * 2 % mod\n\t\t\tbottom = bottom * 2 % mod\n\t\telif int(s[2]) == 3:\n\t\t\tedges = (2 * edges % mod + top) % mod\n\t\t\ttop = bottom\n\t\t\tleft = 2 * left % mod\n\t\t\tright = 2 * right % mod\n\t\telse:\n\t\t\tedges = (2 * edges % mod + bottom) % mod\n\t\t\tbottom = top\n\t\t\tleft = left * 2 % mod\n\t\t\tright = right * 2 % mod\n\telse:\n\t\tprint(edges)\n", "mod = 1000000007\n(n, q) = map(int, input().split())\npot = pow(2, n, mod)\ne = (pot - 1) * 2 % mod\nright = n + 1\nleft = n + 1\ntop = 1\nbottom = pot\nfor _ in range(q):\n\tl = input()\n\tadd = 0\n\tif l[0] == '1':\n\t\tif l[2] == '1':\n\t\t\tadd = right\n\t\t\ttop *= 2\n\t\t\tbottom *= 2\n\t\telif l[2] == '2':\n\t\t\tadd = left\n\t\t\ttop *= 2\n\t\t\tbottom *= 2\n\t\telif l[2] == '3':\n\t\t\tadd = top\n\t\t\tright *= 2\n\t\t\tleft *= 2\n\t\t\ttop = bottom\n\t\telse:\n\t\t\tadd = bottom\n\t\t\tleft *= 2\n\t\t\tright *= 2\n\t\t\tbottom = top\n\t\te = (e * 2 + add) % mod\n\telse:\n\t\tprint(e)\n", "(n, q) = map(int, input().split())\nans = 2 ** (n + 1)\nans = ans - 2\nmod = 1000000007\ntop = 1\nlast = 2 ** n\nheight = n + 1\nfor i in range(q):\n\tty = []\n\tty = list(map(int, input().split()))\n\tif len(ty) == 1:\n\t\tprint(ans % mod)\n\telse:\n\t\tx = ty[1]\n\t\tif x == 1 or x == 2:\n\t\t\tans = 2 * ans + height\n\t\t\tlast = last * 2\n\t\t\ttop = top * 2\n\t\telif x == 3:\n\t\t\tans = 2 * ans + top\n\t\t\ttop = last\n\t\t\theight = 2 * height\n\t\telse:\n\t\t\tans = 2 * ans + last\n\t\t\theight = 2 * height\n\t\t\tlast = top\n", "(n, k) = map(int, input().split())\nb = 2 ** n\nt = 1\nr = n + 1\nnumber_of_edges = (2 ** (n + 1) - 2) % (10 ** 9 + 7)\nfor _ in range(k):\n\tl = list(map(int, input().split()))\n\tif len(l) > 1:\n\t\tif l[1] == 1 or l[1] == 2:\n\t\t\tnumber_of_edges = (number_of_edges * 2 + r) % (10 ** 9 + 7)\n\t\t\t(t, b) = (t * 2, b * 2)\n\t\telif l[1] == 3:\n\t\t\tnumber_of_edges = (number_of_edges * 2 + t) % (10 ** 9 + 7)\n\t\t\tr *= 2\n\t\t\tt = b\n\t\telif l[1] == 4:\n\t\t\tnumber_of_edges = (number_of_edges * 2 + b) % (10 ** 9 + 7)\n\t\t\tr *= 2\n\t\t\tb = t\n\tif len(l) == 1:\n\t\tprint(number_of_edges)\n", "import math\ns = input()\nidx = s.find(' ')\nn = int(s[0:idx])\nq = int(s[idx + 1:])\nr = n + 1\nd = math.floor(pow(2, n) + 0.5)\ne = 2 * (math.floor(pow(2, n) + 0.5) - 1)\nu = 1\nMOD = 1000000007\nfor i in range(0, q):\n\tk = input()\n\tk1 = int(k[0])\n\tif k1 == 1:\n\t\tx = int(k[2])\n\t\tif x == 1 or x == 2:\n\t\t\te = 2 * e + r\n\t\t\tu = 2 * u\n\t\t\td = 2 * d\n\t\telif x == 3:\n\t\t\te = 2 * e + u\n\t\t\tr = r * 2\n\t\t\tu = d\n\t\telse:\n\t\t\te = 2 * e + d\n\t\t\tr = r * 2\n\t\t\td = u\n\telse:\n\t\tprint(e % MOD)\n", "(n, q) = [int(x) for x in input().split()]\nl1 = [1, pow(2, n), n + 1, n + 1]\ndict1 = {1: 2, 2: 3, 3: 0, 4: 1}\nsum1 = pow(2, n + 1) - 2\nflag = 0\nfor _ in range(q):\n\tqu = input()\n\tif int(qu[0]) == 2:\n\t\tprint(sum1 % 1000000007)\n\telse:\n\t\tnum = int(qu[2])\n\t\tsum1 = 2 * sum1 + l1[dict1[num]]\n\t\tif num > 2:\n\t\t\tflag += 1\n\t\t\tl1[2] = 2 * l1[2]\n\t\t\tl1[3] = 2 * l1[3]\n\t\t\tif num == 3 and flag == 1:\n\t\t\t\tl1[0] = l1[1]\n\t\t\t\tflag += 1\n\t\t\telif num == 4 and flag == 1:\n\t\t\t\tl1[1] = l1[0]\n\t\t\t\tflag += 1\n\t\telse:\n\t\t\tl1[0] = 2 * l1[0]\n\t\t\tl1[1] = 2 * l1[1]\n", "from sys import *\n(n, q) = list(map(int, input().strip().split(' ')))\nans = 1000000007\nleaves = 2 ** n\nedges = (2 ** (n + 1) - 2) % ans\nheight = n + 1\nop = []\nroot = 1\nfor i in range(q):\n\ts = str(input().strip())\n\tif s[0] == '2':\n\t\top.append('disp')\n\telse:\n\t\tk = list(map(int, s.split()))\n\t\top.append(k[1])\nfor j in op:\n\tif j == 'disp':\n\t\tprint(edges)\n\telif j == 1 or j == 2:\n\t\tedges = (2 * edges + height) % ans\n\t\tleaves = 2 * leaves % ans\n\t\troot = root * 2 % ans\n\telif j == 4:\n\t\tedges = (2 * edges + leaves) % ans\n\t\tleaves = root\n\t\theight = 2 * height % ans\n\telse:\n\t\tedges = (2 * edges + root) % ans\n\t\troot = leaves\n\t\theight = 2 * height % ans\n", "MOD = 1000000007\n(levels, q) = input().split()\nlevels = int(levels)\nq = int(q)\nleft = levels + 1\nright = levels + 1\ntop = 1\nbottom = pow(2, levels)\nedges = 0\nf = 1\nfor i in range(1, levels + 1):\n\tf = 2 % MOD * (f % MOD) % MOD\n\tedges += f\nlevels += 1\nfor i in range(1, q + 1):\n\tl1 = list(map(int, input().split()))\n\tif l1[0] == 1:\n\t\ty = l1[1]\n\t\tif y == 1:\n\t\t\tedges = edges % MOD * (2 % MOD) % MOD\n\t\t\tedges = (edges % MOD + levels % MOD) % MOD\n\t\t\ttop = top % MOD * (2 % MOD) % MOD\n\t\t\tbottom = bottom % MOD * (2 % MOD) % MOD\n\t\telif y == 2:\n\t\t\tedges = edges % MOD * (2 % MOD) % MOD\n\t\t\tedges = (edges % MOD + levels % MOD) % MOD\n\t\t\ttop = top % MOD * (2 % MOD) % MOD\n\t\t\tbottom = bottom % MOD * (2 % MOD) % MOD\n\t\telif y == 3:\n\t\t\tedges = edges % MOD * (2 % MOD) % MOD\n\t\t\tedges = (edges % MOD + top % MOD) % MOD\n\t\t\ttop = bottom\n\t\t\tlevels = levels % MOD * (2 % MOD)\n\t\telif y == 4:\n\t\t\tedges = edges % MOD * (2 % MOD) % MOD\n\t\t\tedges = (edges % MOD + bottom % MOD) % MOD\n\t\t\tbottom = top\n\t\t\tlevels = levels % MOD * (2 % MOD)\n\telif l1[0] == 2:\n\t\tprint(edges % MOD)\n", "n = list(map(int, input().split()))\n(a, q) = (n[0], n[1])\nn = a\nr = int(n + 1)\nb = 2 ** n\nedge = 2 ** (n + 1) - 2\nu = 1\nl = n\nM = 1000000007\ni = 0\nwhile i < q:\n\ts = list(map(int, input().split()))\n\tif s[0] == 2:\n\t\tprint(edge % M)\n\telif s[1] == 1 or s[1] == 2:\n\t\tedge = edge * 2 % M\n\t\tedge = (edge + r) % M\n\t\tb = b * 2 % M\n\t\tu = u * 2 % M\n\telif s[1] == 3:\n\t\tedge = edge * 2 % M\n\t\tedge = (edge + u) % M\n\t\tu = b\n\t\tr = r * 2 % M\n\t\tl = l * 2 % M\n\telse:\n\t\tedge = edge * 2 % M\n\t\tedge = (edge + b) % M\n\t\tb = u\n\t\tr = r * 2 % M\n\t\tl = l * 2 % M\n\ti += 1\n", "(depth, queries) = map(int, input().strip().split())\nmod = 1000 * 1000 * 1000 + 7\nleft = depth + 1\nright = depth + 1\nup = 1\ndown = pow(2, depth)\nedges = pow(2, depth + 1) - 2\nfor i in range(queries):\n\ttyp = input()\n\tif int(typ[0]) == 1:\n\t\tx = int(typ[2])\n\t\tif x == 1:\n\t\t\tdown = down * 2\n\t\t\tup = up * 2\n\t\t\tedges = edges * 2 + left\n\t\telif x == 2:\n\t\t\tdown = down * 2\n\t\t\tup = up * 2\n\t\t\tedges = edges * 2 + right\n\t\telif x == 3:\n\t\t\tedges = edges * 2 + up\n\t\t\tup = down\n\t\t\tleft = left * 2\n\t\t\tright = right * 2\n\t\telse:\n\t\t\tedges = edges * 2 + down\n\t\t\tdown = up\n\t\t\tleft = left * 2\n\t\t\tright = right * 2\n\telse:\n\t\tprint(edges % mod)\n", "import os, sys\nfrom io import BytesIO, IOBase\n\ndef ii():\n\treturn int(input())\n\ndef si():\n\treturn input()\n\ndef mi():\n\treturn list(map(int, input().split()))\n\ndef li():\n\treturn list(mi())\nimport math\nimport collections\n\ndef CountFrequency(arr):\n\treturn collections.Counter(arr)\nfor i in range(1):\n\t(n, q) = mi()\n\tp = pow(2, n + 1) - 2\n\tt = 1\n\tb = pow(2, n)\n\ts = n + 1\n\tfor i in range(q):\n\t\ta = li()\n\t\tif len(a) == 2:\n\t\t\tif a[1] == 1 or a[1] == 2:\n\t\t\t\tp *= 2\n\t\t\t\tp += s\n\t\t\t\tt *= 2\n\t\t\t\tb *= 2\n\t\t\telse:\n\t\t\t\tp *= 2\n\t\t\t\tif a[1] == 3:\n\t\t\t\t\tp += t\n\t\t\t\t\tt = b\n\t\t\t\t\ts *= 2\n\t\t\t\telse:\n\t\t\t\t\tp += b\n\t\t\t\t\tb = t\n\t\t\t\t\ts *= 2\n\t\telse:\n\t\t\tprint(p % 1000000007)\n", "(n, q) = map(int, input().split())\nedges = pow(2, n + 1) - 2\ntop = 1\nbottom = pow(2, n)\nside = n + 1\nmod = 1000000007\nfor _ in range(q):\n\ts = input()\n\tif s[-1] == '2' and len(s) == 1:\n\t\tprint(edges % mod)\n\telif s[-1] == '1':\n\t\tedges = side + edges * 2\n\t\ttop = 2 * top\n\t\tbottom = 2 * bottom\n\t\tside = side\n\telif s[-1] == '2':\n\t\tedges = side + edges * 2\n\t\ttop = 2 * top\n\t\tbottom = 2 * bottom\n\t\tside = side\n\telif s[-1] == '3':\n\t\tedges = top + edges * 2\n\t\ttop = bottom\n\t\tbottom = bottom\n\t\tside = side * 2\n\telif s[-1] == '4':\n\t\tedges = bottom + edges * 2\n\t\ttop = top\n\t\tbottom = top\n\t\tside = 2 * side\n", "def lisin():\n\ta = list(map(int, input().split()))\n\treturn a\nif 1:\n\t(n, q) = lisin()\n\teds = n + 1\n\tedt = 1\n\tedb = 2 ** n\n\tedtot = 2 * (edb - 1)\n\tfor qq in range(q):\n\t\tx = input().split()\n\t\tif len(x) == 2:\n\t\t\tif x[1] == '1' or x[1] == '2':\n\t\t\t\tedtot *= 2\n\t\t\t\tedtot += eds\n\t\t\t\tedt *= 2\n\t\t\t\tedb *= 2\n\t\t\telif x[1] == '3':\n\t\t\t\tedtot *= 2\n\t\t\t\tedtot += edt\n\t\t\t\tedt = edb\n\t\t\t\teds *= 2\n\t\t\telse:\n\t\t\t\tedtot *= 2\n\t\t\t\tedtot += edb\n\t\t\t\tedb = edt\n\t\t\t\teds *= 2\n\t\telse:\n\t\t\tprint(edtot % 1000000007)\n", "import sys\nmod = 10 ** 9 + 7\n(n, q) = map(int, input().split())\n(u, l, r, d) = (1, n + 1, n + 1, pow(2, n, mod))\ne = 2 * (d - 1) % mod\nfor a in sys.stdin:\n\ta = list(a.split())\n\tif a[0] == '1':\n\t\te = e * 2 % mod\n\t\tif a[1] == '1':\n\t\t\te = (e + r) % mod\n\t\t\tr = l\n\t\t\tu = u * 2 % mod\n\t\t\td = d * 2 % mod\n\t\telif a[1] == '2':\n\t\t\te = (e + l) % mod\n\t\t\tl = r\n\t\t\tu = u * 2 % mod\n\t\t\td = d * 2 % mod\n\t\telif a[1] == '3':\n\t\t\te = (e + u) % mod\n\t\t\tu = d\n\t\t\tl = l * 2 % mod\n\t\t\tr = r * 2 % mod\n\t\telse:\n\t\t\te = (e + d) % mod\n\t\t\td = u\n\t\t\tl = l * 2 % mod\n\t\t\tr = r * 2 % mod\n\telse:\n\t\tprint(e)\n", "(depth, q) = map(int, input().split())\nr = 1000000007\nedges = 0\ntop = 1\nbottom = 2 ** depth\nfor i in range(1, depth + 1):\n\tedges = edges + 2 ** i\nfor i1 in range(0, q):\n\ta = list(map(int, input().split()))\n\tif len(a) == 1:\n\t\tprint(edges % r)\n\telse:\n\t\tx = a[1]\n\t\tif x == 1:\n\t\t\ttop = 2 * top\n\t\t\tbottom = 2 * bottom\n\t\t\tedges = 2 * edges + depth + 1\n\t\telif x == 2:\n\t\t\ttop = top * 2\n\t\t\tbottom = 2 * bottom\n\t\t\tedges = 2 * edges + depth + 1\n\t\telif x == 3:\n\t\t\tdepth = 2 * depth + 1\n\t\t\tedges = 2 * edges + top\n\t\t\ttop = bottom\n\t\telse:\n\t\t\tdepth = 2 * depth + 1\n\t\t\tedges = 2 * edges + bottom\n\t\t\tbottom = top\n", "mod = 1000000007\n(n, q) = map(int, input().split())\nl = n + 1 % mod\nr = n + 1 % mod\nt = 1 % mod\nb = pow(2, n) % mod\ne = (pow(2, n + 1) - 2) % mod\nfor _ in range(q):\n\tlst = list(map(int, input().split()))\n\tif len(lst) != 1:\n\t\tif lst[1] == 1:\n\t\t\te = (2 * e + l) % mod\n\t\t\tl = l\n\t\t\tr = r\n\t\t\tt = 2 * t % mod\n\t\t\tb = 2 * b % mod\n\t\tif lst[1] == 2:\n\t\t\te = (2 * e + r) % mod\n\t\t\tl = l\n\t\t\tr = r\n\t\t\tt = 2 * t % mod\n\t\t\tb = 2 * b % mod\n\t\tif lst[1] == 3:\n\t\t\te = (2 * e + t) % mod\n\t\t\tt = b % mod\n\t\t\tl = 2 * l % mod\n\t\t\tr = 2 * r % mod\n\t\t\tb = b % mod\n\t\tif lst[1] == 4:\n\t\t\te = (2 * e + b) % mod\n\t\t\tb = t % mod\n\t\t\tl = 2 * l % mod\n\t\t\tr = 2 * r % mod\n\t\t\tb = b % mod\n\telse:\n\t\tprint(e)\n", "(n, q) = map(int, input().split())\nli = list()\ned = 2 ** (n + 1) - 2\nrig = n + 1\nlef = n + 1\ntop = 1\nbot = 2 ** n\nfor _ in range(q):\n\tli = list(map(int, input().split()))\n\tif li[0] == 1:\n\t\tif li[1] == 1:\n\t\t\ted = 2 * ed + rig\n\t\t\trig = lef\n\t\t\ttop *= 2\n\t\t\tbot *= 2\n\t\telif li[1] == 2:\n\t\t\ted = 2 * ed + lef\n\t\t\tlef = rig\n\t\t\ttop *= 2\n\t\t\tbot *= 2\n\t\telif li[1] == 3:\n\t\t\ted = 2 * ed + top\n\t\t\ttop = bot\n\t\t\trig *= 2\n\t\t\tlef *= 2\n\t\telif li[1] == 4:\n\t\t\ted = 2 * ed + bot\n\t\t\tbot = top\n\t\t\trig *= 2\n\t\t\tlef *= 2\n\t\ted = ed % 1000000007\n\t\ttop %= 1000000007\n\t\tbot %= 1000000007\n\t\trig %= 1000000007\n\t\tlef %= 1000000007\n\telse:\n\t\tprint(ed % 1000000007)\n", "import math\nnq = input()\nnq = nq.split()\nn = int(nq[0])\nq = int(nq[1])\nsum = 2 * (pow(2, n) - 1)\nbottomedge = pow(2, n)\ndepthedge = n + 1\ntopedge = 1\nwhile q > 0:\n\tq -= 1\n\ta = input()\n\ta = a.split()\n\tif len(a) == 2:\n\t\tx = int(a[1])\n\t\tif x == 2 or x == 1:\n\t\t\tsum = sum % 1000000007\n\t\t\tsum = sum * 2 + depthedge\n\t\t\tbottomedge *= 2\n\t\t\ttopedge *= 2\n\t\telif x == 3:\n\t\t\tsum = sum % 1000000007\n\t\t\tsum = sum * 2 + topedge\n\t\t\ttopedge = bottomedge\n\t\t\tdepthedge *= 2\n\t\telif x == 4:\n\t\t\tsum = sum % 1000000007\n\t\t\tsum = sum * 2 + bottomedge\n\t\t\tbottomedge = topedge\n\t\t\tdepthedge *= 2\n\telif len(a) == 1:\n\t\tsum = sum % 1000000007\n\t\tprint(sum)\n", "(n, q) = list(map(int, input().strip().split()))\nn += 1\ns = n\nb = 2 ** (n - 1)\ne = 2 * (2 ** (n - 1) - 1) if n > 1 else 0\nt = 1\nmod = 1000000007\nfor x in range(q):\n\ti = input().strip().split()\n\tif len(i) == 1:\n\t\tprint(e % mod)\n\telse:\n\t\te *= 2\n\t\tif int(i[1]) <= 2:\n\t\t\te += s\n\t\t\tb *= 2\n\t\t\tt *= 2\n\t\telif int(i[1]) == 4:\n\t\t\ts *= 2\n\t\t\te += b\n\t\t\tb = t\n\t\telse:\n\t\t\ts *= 2\n\t\t\te += t\n\t\t\tt = b\n\t\te %= mod\n", "s = input()\nl = list(s.split())\nn = 0\nq = 0\nn = int(l[0])\nq = int(l[1])\nedges = 0\nleft = 0\nright = 0\nbottom = 0\ntop = 0\nedges = pow(2, n + 1) - 2\nleft = n + 1\nright = n + 1\ntop = 1\nbottom = pow(2, n)\nfor i in range(0, q):\n\tb = input()\n\tl1 = list(b.split())\n\tb1 = int(l1[0])\n\tif b1 == 1:\n\t\ta = int(l1[1])\n\t\tif a == 1:\n\t\t\tedges = 2 * edges + right\n\t\t\tbottom = 2 * bottom\n\t\t\ttop = 2 * top\n\t\telif a == 2:\n\t\t\tedges = 2 * edges + left\n\t\t\tbottom = 2 * bottom\n\t\t\ttop = 2 * top\n\t\telif a == 3:\n\t\t\tedges = 2 * edges + top\n\t\t\ttop = bottom\n\t\t\tleft = 2 * left\n\t\t\tright = 2 * right\n\t\telif a == 4:\n\t\t\tedges = 2 * edges + bottom\n\t\t\tbottom = top\n\t\t\tleft = 2 * left\n\t\t\tright = 2 * right\n\telse:\n\t\tprint(edges % 1000000007)\n", "(n, m) = map(int, input().split())\nedge = pow(2, n + 1, 10 ** 9 + 7)\nedge = (edge - 2) % (10 ** 9 + 7)\ntopnodes = 1\nbottomnodes = 2 ** n\nn += 1\nfor i in range(m):\n\ta = list(map(int, input().split()))\n\tif a[0] == 1:\n\t\tif a[1] == 1:\n\t\t\tedge = (edge * 2 + n) % 1000000007\n\t\t\tbottomnodes *= 2\n\t\t\ttopnodes *= 2\n\t\tif a[1] == 2:\n\t\t\tedge = (edge * 2 + n) % 1000000007\n\t\t\tbottomnodes *= 2\n\t\t\ttopnodes *= 2\n\t\tif a[1] == 3:\n\t\t\tedge = (edge * 2 + topnodes) % 1000000007\n\t\t\ttopnodes = bottomnodes\n\t\t\tbottomnodes = bottomnodes\n\t\t\tn *= 2\n\t\tif a[1] == 4:\n\t\t\tedge = (edge * 2 + bottomnodes) % 1000000007\n\t\t\tbottomnodes = topnodes\n\t\t\ttopnodes = topnodes\n\t\t\tn *= 2\n\telse:\n\t\tprint(edge)\n", "(n, q) = map(int, input().strip().split())\nmod = 1000000007\nt = 1\nb = pow(2, n)\nl = n + 1\nr = n + 1\ned = pow(2, n + 1) - 2\nfor w in range(q):\n\ts = input()\n\tif s == '2':\n\t\tprint(ed % mod)\n\telse:\n\t\tval = s[2]\n\t\tval = int(val)\n\t\tif val == 1:\n\t\t\ted += ed + r\n\t\t\tt += t\n\t\t\tb += b\n\t\tif val == 2:\n\t\t\ted += ed + l\n\t\t\tt += t\n\t\t\tb += b\n\t\tif val == 3:\n\t\t\ted += ed + t\n\t\t\tt = b\n\t\t\tl += l\n\t\t\tr += r\n\t\tif val == 4:\n\t\t\ted += ed + b\n\t\t\tb = t\n\t\t\tl += l\n\t\t\tr += r\n", "def main():\n\t(n, q) = map(int, input().split())\n\tedges = (pow(2, n, 1000000007) - 1) * 2 % 1000000007\n\tbottom = pow(2, n, 1000000007)\n\ttop = 1\n\tright = n + 1\n\tleft = n + 1\n\tfor i in range(q):\n\t\tquery = list(map(int, input().split()))\n\t\tif len(query) == 1:\n\t\t\tprint(edges)\n\t\telse:\n\t\t\top = query[1]\n\t\t\tif op == 1:\n\t\t\t\tedges *= 2\n\t\t\t\tedges += right\n\t\t\t\tedges = edges % 1000000007\n\t\t\t\tbottom *= 2\n\t\t\t\ttop *= 2\n\t\t\telif op == 2:\n\t\t\t\tedges *= 2\n\t\t\t\tedges += left\n\t\t\t\tedges = edges % 1000000007\n\t\t\t\tbottom *= 2\n\t\t\t\ttop *= 2\n\t\t\telif op == 3:\n\t\t\t\tedges *= 2\n\t\t\t\tedges += top\n\t\t\t\tedges = edges % 1000000007\n\t\t\t\tleft *= 2\n\t\t\t\tright *= 2\n\t\t\t\ttop = bottom\n\t\t\telse:\n\t\t\t\tedges *= 2\n\t\t\t\tedges += bottom\n\t\t\t\tedges = edges % 1000000007\n\t\t\t\tleft *= 2\n\t\t\t\tright *= 2\n\t\t\t\tbottom = top\n\t\t\tleft = left % 1000000007\n\t\t\tright = right % 1000000007\n\t\t\tbottom = bottom % 1000000007\n\t\t\ttop = top % 1000000007\nmain()\n", "(d, q) = list(map(int, input().split()))\nans = 1000000007\nleaves = 2 ** d\nedges = (2 ** (d + 1) - 2) % ans\nheight = d + 1\nop = []\nroot = 1\nfor i in range(q):\n\ts = input()\n\tif s == '2' or s == '2 ' or s == '2  ':\n\t\top.append('show')\n\telse:\n\t\tk = list(map(int, s.split()))\n\t\top.append(k[1])\nfor j in op:\n\tif j == 'show':\n\t\tprint(edges)\n\telif j == 1 or j == 2:\n\t\tedges = (2 * edges + height) % ans\n\t\tleaves = 2 * leaves % ans\n\t\troot = root * 2 % ans\n\telif j == 4:\n\t\tedges = (2 * edges + leaves) % ans\n\t\tleaves = root\n\t\theight = 2 * height % ans\n\telse:\n\t\tedges = (2 * edges + root) % ans\n\t\troot = leaves\n\t\theight = 2 * height % ans\n", "(n, q) = map(int, input().split())\nans = pow(2, n + 1) - 2\nl = n + 1\nd = pow(2, n)\nu = 1\nfor ii in range(q):\n\ta = list(map(int, input().split()))\n\tif a[0] == 2:\n\t\tprint(ans % 1000000007)\n\telif a[1] == 1 or a[1] == 2:\n\t\tans *= 2\n\t\tans += l\n\t\td *= 2\n\t\tu *= 2\n\telif a[1] == 3:\n\t\tans *= 2\n\t\tans += u\n\t\tu = d\n\t\tl *= 2\n\telif a[1] == 4:\n\t\tans *= 2\n\t\tans += d\n\t\td = u\n\t\tl *= 2\n", "(n, q) = map(int, input().split())\nm = 10 ** 9 + 7\nedges = pow(2, n + 1, m)\nedges = (edges - 2) % m\ndepth = n + 1\ntopnodes = 1\nbottomnodes = 2 ** n\nfor i in range(0, q):\n\tl1 = list(map(int, input().split()))\n\tif len(l1) == 1:\n\t\tprint(edges)\n\telif l1[1] == 1 or l1[1] == 2:\n\t\tedges = edges * 2 % m\n\t\ttopnodes *= 2\n\t\tedges = (edges + depth) % m\n\t\tbottomnodes *= 2\n\telif l1[1] == 3:\n\t\tedges = edges * 2 % m\n\t\tdepth *= 2\n\t\tedges = (edges + topnodes) % m\n\t\ttopnodes = bottomnodes\n\telif l1[1] == 4:\n\t\tedges = edges * 2 % m\n\t\tedges = (edges + bottomnodes) % m\n\t\tbottomnodes = topnodes\n\t\tdepth *= 2\n", "m = pow(10, 9) + 7\nnq = input().split()\nn = int(nq[0])\nq = int(nq[1])\ne = (pow(2, n + 1) - 2) % m\ntop = 1\nbot = pow(2, n)\nr = n + 1\nl = n + 1\nfor qq in range(q):\n\tqu = input().split()\n\tif qu[0] == '2':\n\t\tprint(e)\n\telse:\n\t\tx = int(qu[1])\n\t\tif x == 1:\n\t\t\te = (2 * e + r) % m\n\t\t\ttop = top * 2\n\t\t\tbot = bot * 2\n\t\telif x == 2:\n\t\t\te = (2 * e + l) % m\n\t\t\ttop = top * 2\n\t\t\tbot = bot * 2\n\t\telif x == 3:\n\t\t\te = (2 * e + top) % m\n\t\t\tr = r * 2\n\t\t\tl = l * 2\n\t\t\ttop = bot\n\t\telse:\n\t\t\te = (2 * e + bot) % m\n\t\t\tr = r * 2\n\t\t\tl = l * 2\n\t\t\tbot = top\n", "info = [int(j) for j in input().split()]\ndepth = info[0]\nn = info[1]\nimport math\nlevel = depth + 1\nroot = 1\nleef = int(math.pow(2, depth)) % 1000000007\nedge = int(math.pow(2, level)) % 1000000007 - 2\nfor i in range(n):\n\tl = [int(j) for j in input().split()]\n\tif len(l) == 2:\n\t\tedge *= 2\n\t\tif l[1] <= 2:\n\t\t\tedge = (edge + level) % 1000000007\n\t\t\troot = root * 2 % 1000000007\n\t\t\tleef = leef * 2 % 1000000007\n\t\telif l[1] == 3:\n\t\t\tedge = (edge + root) % 1000000007\n\t\t\troot = leef\n\t\t\tlevel = level * 2 % 1000000007\n\t\telse:\n\t\t\tedge = (edge + leef) % 1000000007\n\t\t\tleef = root\n\t\t\tlevel = level * 2 % 1000000007\n\telse:\n\t\tprint(edge % 1000000007)\n", "import math\nimport bisect\nimport itertools\nimport sys\nI = lambda : sys.stdin.readline()\nmod = 10 ** 9 + 7\n\ndef modu(a, m):\n\tif a % m:\n\t\treturn a % m\n\treturn m\n\ndef mindiff(a):\n\tb = a[:]\n\tb.sort()\n\tm = 10000000000\n\tfor i in range(len(b) - 1):\n\t\tif b[i + 1] - b[i] < m:\n\t\t\tm = b[i + 1] - b[i]\n\treturn m\n\ndef lcm(a, b):\n\treturn a * b // math.gcd(a, b)\n\ndef merge(a, b):\n\ti = 0\n\tj = 0\n\tc = 0\n\tans = []\n\twhile i < len(a) and j < len(b):\n\t\tif a[i] < b[j]:\n\t\t\tans.append(a[i])\n\t\t\ti += 1\n\t\telse:\n\t\t\tans.append(b[j])\n\t\t\tc += len(a) - i\n\t\t\tj += 1\n\tans += a[i:]\n\tans += b[j:]\n\treturn (ans, c)\n\ndef mergesort(a):\n\tif len(a) == 1:\n\t\treturn (a, 0)\n\tmid = len(a) // 2\n\t(left, left_inversion) = mergesort(a[:mid])\n\t(right, right_inversion) = mergesort(a[mid:])\n\t(m, c) = merge(left, right)\n\tc += left_inversion + right_inversion\n\treturn (m, c)\n\ndef is_prime(num):\n\tif num == 1:\n\t\treturn False\n\tif num == 2:\n\t\treturn True\n\tif num == 3:\n\t\treturn True\n\tif num % 2 == 0:\n\t\treturn False\n\tif num % 3 == 0:\n\t\treturn False\n\tt = 5\n\ta = 2\n\twhile t <= int(math.sqrt(num)):\n\t\tif num % t == 0:\n\t\t\treturn False\n\t\tt += a\n\t\ta = 6 - a\n\treturn True\n\ndef ceil(a, b):\n\tif a % b == 0:\n\t\treturn a // b\n\telse:\n\t\treturn a // b + 1\n\ndef ncr1(n, r):\n\ts = 1\n\tfor i in range(min(n - r, r)):\n\t\ts *= n - i\n\t\ts %= mod\n\t\ts *= pow(i + 1, mod - 2, mod)\n\t\ts %= mod\n\treturn s\n(n, q) = map(int, input().split())\ne = (pow(2, n + 1, mod) - 2) % mod\na = [0, n + 1, n + 1, 1, pow(2, n, mod)]\nfor i in range(q):\n\tb = list(map(int, input().split()))\n\tif len(b) == 1:\n\t\tprint(e)\n\telse:\n\t\t(x, y) = (b[0], b[1])\n\t\te = 2 * e + a[y]\n\t\te %= mod\n\t\tif y < 3:\n\t\t\ta[3] *= 2\n\t\t\ta[4] *= 2\n\t\t\ta[4] %= mod\n\t\t\ta[3] %= mod\n\t\telse:\n\t\t\ta[2] *= 2\n\t\t\ta[1] *= 2\n\t\t\ta[2] %= mod\n\t\t\ta[1] %= mod\n\t\t\tif y == 3:\n\t\t\t\ta[3] = a[4]\n\t\t\telse:\n\t\t\t\ta[4] = a[3]\n", "def mirror_down(e, r, l, u, d):\n\tedge = 2 * e + d\n\tright = r * 2\n\tleft = l * 2\n\tup = u\n\tdown = u\n\treturn [edge, right, left, up, down]\n\ndef mirror_up(e, r, l, u, d):\n\tedge = 2 * e + u\n\tright = r * 2\n\tleft = l * 2\n\tup = d\n\tdown = d\n\treturn [edge, right, left, up, down]\n\ndef mirror_left(e, r, l, u, d):\n\tedge = 2 * e + l\n\tright = r\n\tleft = l\n\tup = u * 2\n\tdown = d * 2\n\treturn [edge, right, left, up, down]\n\ndef mirror_right(e, r, l, u, d):\n\tedge = 2 * e + r\n\tright = r\n\tleft = l\n\tup = u * 2\n\tdown = d * 2\n\treturn [edge, right, left, up, down]\ns = input('').split(' ')\n(n, q) = (int(s[0]), int(s[1]))\ne = 2 ** (n + 1) - 2\nl = n + 1\nr = n + 1\nu = 1\nd = 2 ** n\nwhile q != 0:\n\ts = input('').split(' ')\n\tif len(s) == 2:\n\t\tc = int(s[1])\n\t\tif c == 1:\n\t\t\ta = mirror_right(e, r, l, u, d)\n\t\t\te = a[0]\n\t\t\tr = a[1]\n\t\t\tl = a[2]\n\t\t\tu = a[3]\n\t\t\td = a[4]\n\t\tif c == 2:\n\t\t\ta = mirror_left(e, r, l, u, d)\n\t\t\te = a[0]\n\t\t\tr = a[1]\n\t\t\tl = a[2]\n\t\t\tu = a[3]\n\t\t\td = a[4]\n\t\tif c == 3:\n\t\t\ta = mirror_up(e, r, l, u, d)\n\t\t\te = a[0]\n\t\t\tr = a[1]\n\t\t\tl = a[2]\n\t\t\tu = a[3]\n\t\t\td = a[4]\n\t\tif c == 4:\n\t\t\ta = mirror_down(e, r, l, u, d)\n\t\t\te = a[0]\n\t\t\tr = a[1]\n\t\t\tl = a[2]\n\t\t\tu = a[3]\n\t\t\td = a[4]\n\telse:\n\t\tprint(e % 1000000007)\n\tq -= 1\n", "mod = 10 ** 9 + 7\n(n, q) = map(int, input().split())\ntopbreadth = 1\nbottombreadth = pow(2, n, mod)\nheight = n + 1\nedge = 2 * (pow(2, n, mod) - 1) % mod\ncount1 = 0\ncount2 = 0\nfor i in range(q):\n\ts = input().split()\n\tif len(s) == 2:\n\t\ttyp = int(s[1])\n\t\tif typ == 1 or typ == 2:\n\t\t\tedge *= 2\n\t\t\tedge += height\n\t\t\tbottombreadth *= 2\n\t\t\ttopbreadth *= 2\n\t\t\ttopbreadth %= mod\n\t\t\tbottombreadth %= mod\n\t\t\tedge %= mod\n\t\telif typ == 3:\n\t\t\tedge *= 2\n\t\t\tedge += topbreadth\n\t\t\ttopbreadth = bottombreadth\n\t\t\theight *= 2\n\t\t\theight %= mod\n\t\t\tedge %= mod\n\t\telse:\n\t\t\tedge *= 2\n\t\t\tedge += bottombreadth\n\t\t\tbottombreadth = topbreadth\n\t\t\theight *= 2\n\t\t\theight %= mod\n\t\t\tedge %= mod\n\telse:\n\t\tprint(edge)\n", "m = 10 ** 9 + 7\n(n, q) = map(int, input().split())\nans = 2 * (2 ** n - 1)\nlv = 2 ** n\nsd = n + 1\ntp = 1\nfor i in range(q):\n\ts = input()\n\tif s[0] == '2':\n\t\tprint(ans % m)\n\telse:\n\t\tx = int(s[2])\n\t\tif x == 1 or x == 2:\n\t\t\tans = ans * 2 + sd\n\t\t\tlv *= 2\n\t\t\ttp *= 2\n\t\tif x == 4:\n\t\t\tans = ans * 2 + lv\n\t\t\tsd *= 2\n\t\t\tlv = tp\n\t\tif x == 3:\n\t\t\tans = ans * 2 + tp\n\t\t\tsd *= 2\n\t\t\ttp = lv\n", "s = input()\nn1 = list(map(int, s.split()))\nn = n1[0]\nq = n1[1]\nnodes = 2 ** (n + 1) - 1\nedges = nodes - 1\nr = n + 1\nl = n + 1\nt = 1\nb = 2 ** n\nm = 0\nwhile m < q:\n\ts2 = input()\n\tn2 = list(map(int, s2.split()))\n\tif len(s2) == 3 and n2[0] == 1:\n\t\ta = n2[0]\n\t\tx = n2[1]\n\t\tif x == 1:\n\t\t\tedges = edges * 2 + r\n\t\t\tt = t * 2\n\t\t\tb = b * 2\n\t\tif x == 2:\n\t\t\tedges = edges * 2 + l\n\t\t\tt = t * 2\n\t\t\tb = b * 2\n\t\tif x == 3:\n\t\t\tedges = edges * 2 + t\n\t\t\tl = l * 2\n\t\t\tr = r * 2\n\t\t\tt = b\n\t\tif x == 4:\n\t\t\tedges = edges * 2 + b\n\t\t\tl = l * 2\n\t\t\tr = r * 2\n\t\t\tb = t\n\tif len(s2) == 1:\n\t\tif n2[0] == 2:\n\t\t\tprint(edges % 1000000007)\n\tm = m + 1\n", "s = input()\nl = list(s.split())\nn = int(l[0])\nq = int(l[1])\ne = pow(2, n + 1) - 2\nl = n + 1\nr = n + 1\nt = 1\nb = pow(2, n)\nfor i in range(0, q):\n\ty = input()\n\tl6 = list(y.split())\n\ty1 = int(l6[0])\n\tif y1 == 1:\n\t\tx = int(l6[1])\n\t\tif x == 1:\n\t\t\te = 2 * e + r\n\t\t\tb = 2 * b\n\t\t\tt = 2 * t\n\t\telif x == 2:\n\t\t\te = 2 * e + l\n\t\t\tb = 2 * b\n\t\t\tt = 2 * t\n\t\telif x == 3:\n\t\t\te = 2 * e + t\n\t\t\tt = b\n\t\t\tl = 2 * l\n\t\t\tr = 2 * r\n\t\telif x == 4:\n\t\t\te = 2 * e + b\n\t\t\tb = t\n\t\t\tl = 2 * l\n\t\t\tr = 2 * r\n\telse:\n\t\tprint(e % 1000000007)\n", "(n, q) = list(map(int, input().split()))\ntop = 1\nbottom = 2 ** n\ndepth = n + 1\nedges = 2 ** (n + 1) - 2\nfor _ in range(q):\n\tx = list(map(int, input().split()))\n\tif x[0] == 2:\n\t\tprint(edges % (10 ** 9 + 7))\n\telse:\n\t\tt = x[1]\n\t\tedges *= 2\n\t\tif t == 1 or t == 2:\n\t\t\ttop *= 2\n\t\t\tbottom *= 2\n\t\t\tedges += depth\n\t\tif t == 3:\n\t\t\tdepth *= 2\n\t\t\tedges += top\n\t\t\ttop = bottom\n\t\tif t == 4:\n\t\t\tdepth *= 2\n\t\t\tedges += bottom\n\t\t\tbottom = top\n", "m = 10 ** 9 + 7\n(n, q) = map(int, input().split())\nttttttooooppppp = 1\nlllleeeefffttt = n + 1\nrrriiiggghhhttt = n + 1\nbbboootttooommm = 2 ** n\neeeeddddgggeeeessss = (2 ** (n + 1) - 2) % m\nfor _ in range(q):\n\tw = [int(i) for i in input().split()]\n\tif len(w) == 1:\n\t\tprint(eeeeddddgggeeeessss)\n\telse:\n\t\tt = w[1]\n\t\tif t == 1 or t == 2:\n\t\t\tttttttooooppppp *= 2\n\t\t\tbbboootttooommm *= 2\n\t\t\teeeeddddgggeeeessss = (eeeeddddgggeeeessss * 2 + rrriiiggghhhttt) % m\n\t\telif t == 3:\n\t\t\teeeeddddgggeeeessss = (eeeeddddgggeeeessss * 2 + ttttttooooppppp) % m\n\t\t\trrriiiggghhhttt *= 2\n\t\t\tlllleeeefffttt = rrriiiggghhhttt\n\t\t\tttttttooooppppp = bbboootttooommm\n\t\telse:\n\t\t\teeeeddddgggeeeessss = (eeeeddddgggeeeessss * 2 + bbboootttooommm) % m\n\t\t\trrriiiggghhhttt *= 2\n\t\t\tlllleeeefffttt = rrriiiggghhhttt\n\t\t\tbbboootttooommm = ttttttooooppppp\n", "m = 10 ** 9 + 7\n(n, q) = map(int, input().split())\ntop = 1\nleft = n + 1\nright = n + 1\nbottom = 2 ** n\nedges = (2 ** (n + 1) - 2) % m\nfor _ in range(q):\n\tw = [int(i) for i in input().split()]\n\tif len(w) == 1:\n\t\tprint(edges)\n\telse:\n\t\tt = w[1]\n\t\tif t == 1 or t == 2:\n\t\t\ttop *= 2\n\t\t\tbottom *= 2\n\t\t\tedges = (edges * 2 + right) % m\n\t\telif t == 3:\n\t\t\tedges = (edges * 2 + top) % m\n\t\t\tright *= 2\n\t\t\tleft = right\n\t\t\ttop = bottom\n\t\telse:\n\t\t\tedges = (edges * 2 + bottom) % m\n\t\t\tright *= 2\n\t\t\tleft = right\n\t\t\tbottom = top\n", "(n, q) = map(int, input().split())\n(top, bottom, e) = (1, 2 ** n, 2 ** (n + 1) - 2)\nl = []\nfor i in range(q):\n\tl = list(map(int, input().split()))\n\tif l[0] == 2:\n\t\tprint(e % (10 ** 9 + 7))\n\telif l[1] == 1 or l[1] == 2:\n\t\te = e * 2 + (n + 1)\n\t\ttop = top * 2\n\t\tbottom = bottom * 2\n\telif l[1] == 3:\n\t\te = e * 2 + top\n\t\ttop = bottom\n\t\tn = n * 2 + 1\n\telif l[1] == 4:\n\t\te = e * 2 + bottom\n\t\tbottom = top\n\t\tn = n * 2 + 1\n", "d = 1000000007\n(n, q) = map(int, input().split())\nr = 1\nle = 2 ** n\nans = 2 ** (n + 1) - 2\nwhile q > 0:\n\tq -= 1\n\tl = list(map(int, input().split()))\n\tif len(l) == 1:\n\t\tprint(ans % d)\n\telif l[1] == 1 or l[1] == 2:\n\t\tans = (ans * 2 + (n + 1)) % d\n\t\tr = r * 2\n\t\tle = le * 2\n\telif l[1] == 3:\n\t\tans = (ans * 2 + r) % d\n\t\tr = le\n\t\tn = 2 * n + 1\n\telse:\n\t\tans = (ans * 2 + le) % d\n\t\tle = r\n\t\tn = 2 * n + 1\n", "mod = 1000000007\n(n, q) = map(int, input().strip().split(' '))\nn += 1\ndown = pow(2, n - 1, mod)\ntop = 1\ndepth = n\ntop = 1\nfin = down * 2 - 2\nfin %= mod\nfor i in range(q):\n\tarr = list(map(int, input().strip().split(' ')))\n\tif len(arr) == 1:\n\t\tprint(fin)\n\telif arr[1] == 1 or arr[1] == 2:\n\t\tfin = fin * 2\n\t\ttop *= 2\n\t\tdown *= 2\n\t\tfin += depth\n\telse:\n\t\tdepth *= 2\n\t\tfin *= 2\n\t\tif arr[1] == 4:\n\t\t\tfin += down\n\t\t\tdown = top\n\t\telse:\n\t\t\tfin += top\n\t\t\ttop = down\n\tfin %= mod\n\tdown %= mod\n\ttop %= mod\n\tdepth %= mod\n", "MOD = 1000000007\n(n, q) = map(int, input().split())\nnum_edges = 2 * (2 ** n - 1)\nheight = n + 1\ntop = 1\nbottom = 2 ** n\nfor _ in range(q):\n\ts = input()\n\tif s[0] == '1':\n\t\top = s[2]\n\t\tif op in ['1', '2']:\n\t\t\tnum_edges += num_edges + height\n\t\t\ttop *= 2\n\t\t\tbottom *= 2\n\t\telif op == '3':\n\t\t\tnum_edges += num_edges + top\n\t\t\ttop = bottom\n\t\t\theight *= 2\n\t\telse:\n\t\t\tnum_edges += num_edges + bottom\n\t\t\tbottom = top\n\t\t\theight *= 2\n\telse:\n\t\tprint(num_edges % MOD)\n", "(n, q) = map(int, input().split())\nedges = 2 * (2 ** n - 1)\nside_nodes = n + 1\ntop_nodes = 1\nbottom_nodes = 2 ** n\nfor i in range(q):\n\tquery = list(map(int, input().split()))\n\tif query[0] == 1:\n\t\tif query[1] == 1 or query[1] == 2:\n\t\t\tedges = edges * 2 + side_nodes\n\t\t\ttop_nodes *= 2\n\t\t\tbottom_nodes *= 2\n\t\telif query[1] == 3:\n\t\t\tedges = edges * 2 + top_nodes\n\t\t\ttop_nodes = bottom_nodes\n\t\t\tside_nodes *= 2\n\t\telse:\n\t\t\tedges = edges * 2 + bottom_nodes\n\t\t\tbottom_nodes = top_nodes\n\t\t\tside_nodes *= 2\n\telse:\n\t\tprint(edges % 1000000007)\n", "(n, q) = input().split()\n(n, q) = (int(n), int(q))\nrt = 1\nnd = 2 ** (n + 1) - 1\nlf = (nd + 1) // 2\nedge = nd - 1\nn += 1\nfor i in range(int(q)):\n\tch = list(map(int, input().split(' ')))\n\tif len(ch) == 2:\n\t\tmr = ch[1]\n\t\tif mr == 1 or mr == 2:\n\t\t\tedge = edge * 2 + n\n\t\t\tlf = lf * 2\n\t\t\trt = rt * 2\n\t\telif mr == 3:\n\t\t\tedge = edge * 2 + rt\n\t\t\tn = n * 2\n\t\t\trt = lf\n\t\telse:\n\t\t\tedge = edge * 2 + lf\n\t\t\tn = n * 2\n\t\t\tlf = rt\n\telse:\n\t\tprint(edge % (10 ** 9 + 7))\n", "def power(x, y):\n\tif y == 0:\n\t\treturn 1\n\telif int(y % 2) == 0:\n\t\treturn power(x, int(y / 2)) * power(x, int(y / 2))\n\telse:\n\t\treturn x * power(x, int(y / 2)) * power(x, int(y / 2))\n(h, q) = map(int, input().strip().split())\nrht = h + 1\nlft = h + 1\ntop = 1\nedge = power(2, h + 1) - 2\nbottom = power(2, h)\nfor i in range(1, q + 1):\n\ttype = input()\n\tif type == '2':\n\t\tprint(edge % 1000000007)\n\telse:\n\t\ty = type[2]\n\t\ty = int(y)\n\t\tif y == 1:\n\t\t\tedge = edge * 2 + rht\n\t\t\ttop = top * 2\n\t\t\tbottom = bottom * 2\n\t\telif y == 2:\n\t\t\tedge = edge * 2 + lft\n\t\t\ttop = top * 2\n\t\t\tbottom = bottom * 2\n\t\telif y == 3:\n\t\t\tedge = edge * 2 + top\n\t\t\ttop = bottom\n\t\t\tlft = lft * 2\n\t\t\trht = rht * 2\n\t\telif y == 4:\n\t\t\tedge = edge * 2 + bottom\n\t\t\tbottom = top\n\t\t\tlft = lft * 2\n\t\t\trht = rht * 2\n", "def power(x, y, p):\n\tres = 1\n\tx = x % p\n\twhile y > 0:\n\t\tif y & 1 == 1:\n\t\t\tres = res * x % p\n\t\ty = y >> 1\n\t\tx = x * x % p\n\treturn res\n(n, q) = map(int, input().split())\ne = (power(2, n, 10 ** 9 + 7) - 1) * 2\nt = 1\nb = power(2, n, 10 ** 9 + 7)\nr = n + 1\nfor i in range(q):\n\tl = list(map(int, input().split()))\n\tif l[0] == 1:\n\t\tif l[1] == 1 or l[1] == 2:\n\t\t\te = (2 * e + r) % (10 ** 9 + 7)\n\t\t\tb = 2 * b % (10 ** 9 + 7)\n\t\t\tt = 2 * t % (10 ** 9 + 7)\n\t\telif l[1] == 3:\n\t\t\te = (2 * e + t) % (10 ** 9 + 7)\n\t\t\tr = 2 * r % (10 ** 9 + 7)\n\t\t\tt = b % (10 ** 9 + 7)\n\t\telse:\n\t\t\te = (2 * e + b) % (10 ** 9 + 7)\n\t\t\tr = 2 * r % (10 ** 9 + 7)\n\t\t\tb = t % (10 ** 9 + 7)\n\telif l[0] == 2:\n\t\tprint(e)\n", "arr = list(map(int, input().split()))\nh = arr[0]\ne = 2 ** (h + 1)\ne1 = e - 2\nl = h + 1\nr = h + 1\nu = 1\nd = 2 ** h\nwhile arr[1]:\n\tarr[1] = arr[1] - 1\n\tarr1 = list(map(int, input().split()))\n\tif arr1[0] == 2:\n\t\tprint(e1 % 1000000007)\n\telif arr1[1] == 1:\n\t\te1 = e1 * 2\n\t\te1 = e1 + r\n\t\tu = u * 2\n\t\td = d * 2\n\t\te1 = e1 % 1000000007\n\telif arr1[1] == 2:\n\t\te1 = e1 * 2\n\t\te1 = e1 + l\n\t\tu = u * 2\n\t\td = d * 2\n\t\te1 = e1 % 1000000007\n\telif arr1[1] == 3:\n\t\te1 *= 2\n\t\te1 = e1 + u\n\t\tu = d\n\t\tl = l * 2\n\t\tr = r * 2\n\t\te1 = e1 % 1000000007\n\telif arr1[1] == 4:\n\t\te1 *= 2\n\t\te1 = e1 + d\n\t\td = u\n\t\tl = l * 2\n\t\tr = r * 2\n\t\te1 = e1 % 1000000007\n", "(n, q) = map(int, input().split())\ne = 2 ** (n + 1) - 2\nl = 2 ** n\nh = n + 1\np = 1\nup = 0\ndown = 1\nfor i in range(q):\n\tqi = input().split()\n\tif qi[0] == '2':\n\t\tprint(e % 1000000007)\n\telif qi[1] == '1' or qi[1] == '2':\n\t\te = e * 2 + h\n\t\tl = l * 2\n\t\tp = p * 2\n\telif qi[1] == '3':\n\t\tif up == 1:\n\t\t\te = e * 2 + l\n\t\telse:\n\t\t\te = e * 2 + p\n\t\tup = down\n\t\th = h * 2\n\telse:\n\t\tif down == 1:\n\t\t\te = e * 2 + l\n\t\telse:\n\t\t\te = e * 2 + p\n\t\tdown = up\n\t\th = h * 2\n", "(n, q) = map(int, input().rstrip().split())\nu = 1\nd = 2 ** n\nl = 2 * (2 ** n - 1)\ntr = False\nlt = n + 1\nfor i in range(q):\n\tl = l % 1000000007\n\tte = input().rstrip().split()\n\tif int(te[0]) == 2:\n\t\tprint(l)\n\telse:\n\t\top = int(te[1])\n\t\tif op == 1 or op == 2:\n\t\t\tu = 2 * u\n\t\t\td = 2 * d\n\t\t\tl = 2 * l + lt\n\t\telif tr:\n\t\t\tl = 2 * l + u\n\t\t\tlt = 2 * lt\n\t\telse:\n\t\t\tif op == 3:\n\t\t\t\tl = 2 * l + u\n\t\t\t\tlt = lt * 2\n\t\t\t\tu = d\n\t\t\telse:\n\t\t\t\tl = 2 * l + d\n\t\t\t\tlt = lt * 2\n\t\t\t\td = u\n\t\t\ttr = True\n", "try:\n\t(n, q) = list(map(int, input().split()))\n\t(L, R, T, B) = (n + 1, n + 1, 1, 2 ** n)\n\ttotal = 0\n\tfor val in range(1, n + 1):\n\t\ttotal += 2 ** val\n\tfor _ in range(q):\n\t\ti = list(map(int, input().split()))\n\t\tif i[0] == 1:\n\t\t\tif i[1] == 1:\n\t\t\t\ttotal *= 2\n\t\t\t\ttotal += R\n\t\t\t\t(L, R, T, B) = (L, R, 2 * T, B * 2)\n\t\t\tif i[1] == 2:\n\t\t\t\ttotal *= 2\n\t\t\t\ttotal += L\n\t\t\t\t(L, R, T, B) = (L, R, 2 * T, B * 2)\n\t\t\tif i[1] == 3:\n\t\t\t\ttotal *= 2\n\t\t\t\ttotal += T\n\t\t\t\t(L, R, T, B) = (2 * L, 2 * R, B, B)\n\t\t\tif i[1] == 4:\n\t\t\t\ttotal *= 2\n\t\t\t\ttotal += B\n\t\t\t\t(L, R, T, B) = (2 * L, 2 * R, T, T)\n\t\telse:\n\t\t\tprint(total % 1000000007)\nexcept:\n\tpass\n", "def power(x, y, p):\n\tres = 1\n\tx = x % p\n\twhile y > 0:\n\t\tif y & 1 == 1:\n\t\t\tres = res * x % p\n\t\ty = y >> 1\n\t\tx = x * x % p\n\treturn res\n[n, q] = [int(i) for i in input().split()]\nsu = (power(2, n + 1, 1000000007) - 2 + 1000000007) % 1000000007\nwidth = 1\nt = 0\nk = n + 1\nwhile q > 0:\n\ta = [int(i) for i in input().split()]\n\tif a[0] == 2:\n\t\tprint(su)\n\telif a[1] == 1 or a[1] == 2:\n\t\tsu = (2 * su % 1000000007 + k % 1000000007) % 1000000007\n\t\twidth = width * 2 % 1000000007\n\telif a[1] == 3:\n\t\tif t == 0:\n\t\t\tsu = (2 * su % 1000000007 + width % 1000000007) % 1000000007\n\t\t\tt = 1\n\t\telif t == 1:\n\t\t\tsu = (2 * su % 1000000007 + width % 1000000007 * power(2, n, 1000000007) % 1000000007) % 1000000007\n\t\telif t == 2:\n\t\t\tsu = (2 * su % 1000000007 + width % 1000000007) % 1000000007\n\t\tk = k * 2 % 1000000007\n\telif a[1] == 4:\n\t\tif t == 2:\n\t\t\tsu = (2 * su % 1000000007 + width % 1000000007) % 1000000007\n\t\telif t == 0:\n\t\t\tsu = (2 * su % 1000000007 + width % 1000000007 * power(2, n, 1000000007) % 1000000007) % 1000000007\n\t\t\tt = 2\n\t\telif t == 1:\n\t\t\tsu = (2 * su % 1000000007 + width % 1000000007 * power(2, n, 1000000007) % 1000000007) % 1000000007\n\t\tk = k * 2 % 1000000007\n\tq -= 1\n", "(n, q) = input().split()\nn = int(n)\nq = int(q)\nr = n + 1\nl = n + 1\nb = 2 ** n\nt = 1\nedge = 0\nMOD = 1000000007\nfor i in range(1, n + 1):\n\tedge += 2 ** i\nfor i in range(q):\n\tl1 = list(map(int, input().split()))\n\tif l1[0] == 1:\n\t\tif l1[1] == 1:\n\t\t\tedge = (edge % MOD * 2 + r) % MOD\n\t\t\tr = r % MOD\n\t\t\tl = l % MOD\n\t\t\tb = 2 * (b % MOD)\n\t\t\tt = 2 * (t % MOD)\n\t\telif l1[1] == 2:\n\t\t\tedge = (edge % MOD * 2 + l) % MOD\n\t\t\tr = r % MOD\n\t\t\tl = l % MOD\n\t\t\tb = 2 * (b % MOD)\n\t\t\tt = 2 * (t % MOD)\n\t\telif l1[1] == 3:\n\t\t\tedge = (edge % MOD * 2 + t) % MOD\n\t\t\tt = b % MOD\n\t\t\tb = b % MOD\n\t\t\tr = 2 * (r % MOD)\n\t\t\tl = 2 * (l % MOD)\n\t\telif l1[1] == 4:\n\t\t\tedge = (edge % MOD * 2 + b) % MOD\n\t\t\tb = t % MOD\n\t\t\tt = t % MOD\n\t\t\tr = 2 * (r % MOD)\n\t\t\tl = 2 * (l % MOD)\n\telse:\n\t\tprint(edge % MOD)\n", "import math\n(n, q) = map(int, input().split())\nedg = 2 ** (n + 1) - 2\nh = n + 1\ntop = 1\nbot = 2 ** n\nfor i in range(q):\n\ta = list(map(int, input().split()))\n\tif len(a) == 2:\n\t\tif a[1] == 1 or a[1] == 2:\n\t\t\tedg = 2 * edg + h\n\t\t\tbot = 2 * bot\n\t\t\ttop = 2 * top\n\t\telif a[1] == 3:\n\t\t\tedg = 2 * edg + top\n\t\t\th = 2 * h\n\t\t\ttop = bot\n\t\telif a[1] == 4:\n\t\t\tedg = 2 * edg + bot\n\t\t\tbot = top\n\t\t\th = 2 * h\n\telse:\n\t\tprint(edg % 1000000007)\n", "(n, q) = [int(a) for a in input().split()]\ne = pow(2, n + 1) - 2\nl = [1, pow(2, n), n + 1, n + 1]\nd = {1: 2, 2: 3, 3: 0, 4: 1}\nf = 0\nfor _ in range(q):\n\tx = input()\n\tif int(x[0]) == 2:\n\t\tprint(e % 1000000007)\n\telse:\n\t\tx1 = int(x[2])\n\t\te = 2 * e + l[d[x1]]\n\t\tif x1 > 2:\n\t\t\tf = f + 1\n\t\t\tl[2] = 2 * l[2]\n\t\t\tl[3] = 2 * l[3]\n\t\t\tif x1 == 3 and f == 1:\n\t\t\t\tl[0] = l[1]\n\t\t\t\tf = f + 1\n\t\t\telif x1 == 4 and f == 1:\n\t\t\t\tl[1] = l[0]\n\t\t\t\tf = f + 1\n\t\telse:\n\t\t\tl[0] = 2 * l[0]\n\t\t\tl[1] = 2 * l[1]\n", "(n, q) = map(int, input().split())\ntopNodes = 1\nbottomNodes = 2 ** n\nleftNodes = n + 1\nrightNodes = n + 1\nedges = 2 ** (n + 1) - 2\nfor i in range(q):\n\tinp = input()\n\tif len(inp) > 1:\n\t\t(cmd, dir) = map(int, inp.split())\n\t\tif dir == 1:\n\t\t\tedges = 2 * edges + rightNodes\n\t\t\tbottomNodes = 2 * bottomNodes\n\t\t\ttopNodes = 2 * topNodes\n\t\telif dir == 2:\n\t\t\tedges = 2 * edges + leftNodes\n\t\t\tbottomNodes = 2 * bottomNodes\n\t\t\ttopNodes = 2 * topNodes\n\t\telif dir == 3:\n\t\t\tedges = 2 * edges + topNodes\n\t\t\tleftNodes = 2 * leftNodes\n\t\t\trightNodes = 2 * rightNodes\n\t\t\ttopNodes = bottomNodes\n\t\telif dir == 4:\n\t\t\tedges = 2 * edges + bottomNodes\n\t\t\tleftNodes = 2 * leftNodes\n\t\t\trightNodes = 2 * rightNodes\n\t\t\tbottomNodes = topNodes\n\telse:\n\t\tprint(edges % 1000000007)\n", "(n, q) = map(int, input().split())\nc = 2 * (pow(2, n) - 1)\nns = n + 1\nnt = 1\nnb = pow(2, n)\nx = 7 + pow(10, 9)\nfor i in range(q):\n\tli = list(map(int, input().split()))\n\tif len(li) == 1:\n\t\tprint(c % x)\n\telse:\n\t\tb = li[1]\n\t\tif b == 1 or b == 2:\n\t\t\tc = 2 * c + ns\n\t\t\tnt *= 2\n\t\t\tnb *= 2\n\t\telif b == 3:\n\t\t\tc = 2 * c + nt\n\t\t\tns *= 2\n\t\t\tnt = nb\n\t\telse:\n\t\t\tc = 2 * c + nb\n\t\t\tns *= 2\n\t\t\tnb = nt\n"]

raw_tags: ['Mathematics', 'Basic Maths', 'Algorithms', 'Modular Exponentiation', 'Constructive', 'ad-hoc', 'Modular Arithmetic']

source: codechef

tags: ['Number theory', 'Constructive algorithms', 'Mathematics', 'Ad-hoc']

time_limit: 1 seconds

memory_limit: 50000 bytes

raw_problem:
Given a Complete Binary Tree of ‘n’ depth, you can perform 4 types of mirror operation on the tree:-
Mirror on the right. The tree is mirrored to the right and rightmost node on every level is connected with the mirrored corresponding node.
Mirror on the left. The tree is mirrored to the left and leftmost node on every level is connected with the mirrored corresponding node.
Mirror on the top. The tree is mirrored to the top and topmost nodes are connected with corresponding nodes.
Mirror on the bottom. The tree is mirrored to the bottom and bottom most nodes are connected with the corresponding nodes.
See the image for details.

Mirror Right:

Mirror Bottom:

You are given ‘q’ queries, each performing this type of operation or asking for the no of edges in the produced graph.
Queries are of the form “1 x” or “2” where x is 1 for right, 2 for left, 3 for top or 4 for bottom.
1 x:  Perform x operation on the result graph.
2:     Print the no of edges in the graph. Since it can be very large, print it modulo 1000000007.

###Input:

- First line will contain $n$, the depth of the initial tree and $q$, the number of queries.
-  Next $q$ lines contain queries of the form "1 $x$" or "2".

###Output:
For each query of type "2", output a single line containing the no of edges in the graph modulo 1000000007.

###Constraints
- $1 \leq n \leq 1000$
- $1 \leq q \leq 10^5$
- $1 \leq x \leq 4$

###Sample Input:
	2 3
	1 1
	1 4
	2

###Sample Output:
	38

###EXPLANATION:
Initial no of edges = 6
After the operation 1 1, no of edges = 15
After the operation 1 4, no of edges = 38
At operation 2, we print the no of edges that is 38.

All submissions for this problem are available.

question:
Given a Complete Binary Tree of ‘n’ depth, you can perform 4 types of mirror operation on the tree:-
Mirror on the right. The tree is mirrored to the right and rightmost node on every level is connected with the mirrored corresponding node.
Mirror on the left. The tree is mirrored to the left and leftmost node on every level is connected with the mirrored corresponding node.
Mirror on the top. The tree is mirrored to the top and topmost nodes are connected with corresponding nodes.
Mirror on the bottom. The tree is mirrored to the bottom and bottom most nodes are connected with the corresponding nodes.
See the image for details.

Mirror Right:

![image](1.png)

Mirror Bottom:

![image](2.png)

You are given ‘q’ queries, each performing this type of operation or asking for the no of edges in the produced graph.
Queries are of the form “1 x” or “2” where x is 1 for right, 2 for left, 3 for top or 4 for bottom.
1 x:  Perform x operation on the result graph.
2:     Print the no of edges in the graph. Since it can be very large, print it modulo 1000000007.

###Input:

- First line will contain $n$, the depth of the initial tree and $q$, the number of queries.
-  Next $q$ lines contain queries of the form "1 $x$" or "2".

###Output:
For each query of type "2", output a single line containing the no of edges in the graph modulo 1000000007.

###Constraints
- $1 \leq n \leq 1000$
- $1 \leq q \leq 10^5$
- $1 \leq x \leq 4$

###Sample Input:
	2 3
	1 1
	1 4
	2

###Sample Output:
	38

###EXPLANATION:
Initial no of edges = 6
After the operation 1 1, no of edges = 15
After the operation 1 4, no of edges = 38
At operation 2, we print the no of edges that is 38.

All submissions for this problem are available.

image_tags: Tree Graph

data_split: test


Crossing Prisms

source: ACM International Collegiate Programming Contest, Asia Regional 2004, Japan

raw_problem:
Problem I: Crossing Prisms

Prof. Bocchan is a mathematician and a sculptor. He likes to create sculptures with mathematics.

His style to make sculptures is very unique. He uses two identical prisms. Crossing them at right
angles, he makes a polyhedron that is their intersection as a new work. Since he finishes it up
with painting, he needs to know the surface area of the polyhedron for estimating the amount
of pigment needed.

For example, let us consider the two identical prisms in Figure 1. The definition of their cross
section is given in Figure 2. The prisms are put at right angles with each other and their
intersection is the polyhedron depicted in Figure 3. An approximate value of its surface area
is 194.8255.

Figure 1: Two identical prisms at right angles

Given the shape of the cross section of the two identical prisms, your job is to calculate the
surface area of his sculpture.

Input

The input consists of multiple datasets, followed by a single line containing only a zero. The
first line of each dataset contains an integer n indicating the number of the following lines, each
of which contains two integers ai and bi (i = 1, ... , n).

Figure 2: Outline of the cross section

Figure 3: The intersection

A closed path formed by the given points (a1, b1), (a2, b2 ), ... , (an, bn), (an+1, bn+1)(= (a1, b1))
indicates the outline of the cross section of the prisms. The closed path is simple, that is, it does
not cross nor touch itself. The right-hand side of the line segment from (ai, bi) to (ai+1 , bi+1 ) is the inside of the section.

You may assume that 3 ≤ n ≤ 4, 0 ≤ ai ≤ 10 and 0 ≤ bi ≤ 10 (i = 1, ... , n).

One of the prisms is put along the x-axis so that the outline of its cross section at x = ζ is
indicated by points (xi, yi, zi ) = (ζ, ai, bi) (0 ≤ ζ ≤ 10, i = 1, ... , n). The other prism is put
along the y-axis so that its cross section at y = η is indicated by points (xi, yi, zi) = (ai, η, bi)
(0 ≤ η ≤ 10, i = 1, ... , n).

Output

The output should consist of a series of lines each containing a single decimal fraction. Each
number should indicate an approximate value of the surface area of the polyhedron defined by the corresponding dataset. The value may contain an error less than or equal to 0.0001. You
may print any number of digits below the decimal point.

Sample Input

4
5 0
0 10
7 5
10 5
4
7 5
10 5
5 0
0 10
4
0 10
10 10
10 0
0 0
3
0 0
0 10
10 0
4
0 10
10 5
0 0
9 5
4
5 0
0 10
5 5
10 10
4
0 5
5 10
10 5
5 0
4
7 1
4 1
0 1
9 5
0

Output for the Sample Input

194.8255
194.8255
600.0000
341.4214
42.9519
182.5141
282.8427
149.2470

source: aizu

question:
Problem I: Crossing Prisms

Prof. Bocchan is a mathematician and a sculptor. He likes to create sculptures with mathematics.

His style to make sculptures is very unique. He uses two identical prisms. Crossing them at right
angles, he makes a polyhedron that is their intersection as a new work. Since he finishes it up
with painting, he needs to know the surface area of the polyhedron for estimating the amount
of pigment needed.

For example, let us consider the two identical prisms in Figure 1. The definition of their cross
section is given in Figure 2. The prisms are put at right angles with each other and their
intersection is the polyhedron depicted in Figure 3. An approximate value of its surface area
is 194.8255.

![image](1.png)
Figure 1: Two identical prisms at right angles

Given the shape of the cross section of the two identical prisms, your job is to calculate the
surface area of his sculpture.

Input

The input consists of multiple datasets, followed by a single line containing only a zero. The
first line of each dataset contains an integer n indicating the number of the following lines, each
of which contains two integers a_{i} and b_{i} (i = 1, ... , n).

![image](2.png)
Figure 2: Outline of the cross section

![image](3.png)
Figure 3: The intersection

A closed path formed by the given points (a_{1}, b_{1}), (a_{2}, b_{2} ), ... , (a_{n}, b_{n}), (a_{n+1}, b_{n+1})(= (a_{1}, b_{1}))
indicates the outline of the cross section of the prisms. The closed path is simple, that is, it does
not cross nor touch itself. The right-hand side of the line segment from (a_{i}, b_{i}) to (a_{i}+1 , b_{i}+1 ) is the inside of the section.

You may assume that 3 ≤ n ≤ 4, 0 ≤ a_{i} ≤ 10 and 0 ≤ b_{i} ≤ 10 (i = 1, ... , n).

One of the prisms is put along the x-axis so that the outline of its cross section at x = ζ is
indicated by points (x_{i}, y_{i}, z_{i} ) = (ζ, a_{i}, b_{i}) (0 ≤ ζ ≤ 10, i = 1, ... , n). The other prism is put
along the y-axis so that its cross section at y = η is indicated by points (x_{i}, y_{i}, z_{i}) = (a_{i}, η, b_{i})
(0 ≤ η ≤ 10, i = 1, ... , n).

Output

The output should consist of a series of lines each containing a single decimal fraction. Each
number should indicate an approximate value of the surface area of the polyhedron defined by the corresponding dataset. The value may contain an error less than or equal to 0.0001. You
may print any number of digits below the decimal point.

Sample Input

4
5 0
0 10
7 5
10 5
4
7 5
10 5
5 0
0 10
4
0 10
10 10
10 0
0 0
3
0 0
0 10
10 0
4
0 10
10 5
0 0
9 5
4
5 0
0 10
5 5
10 10
4
0 5
5 10
10 5
5 0
4
7 1
4 1
0 1
9 5
0

Output for the Sample Input

194.8255
194.8255
600.0000
341.4214
42.9519
182.5141
282.8427
149.2470

image_tags:
3D Geometry
3D Geometry
3D Geometry

data_split: test


B. Table

problem_index: B

time_limit: 4 seconds

memory_limit: 256 megabytes

note:
Let's consider the first test case:
![image](images/cf_232_B/1.png)
5 × 5
20
25
45

solutions: ["(n, m, k) = map(int, input().split())\nM = int(1000000000.0 + 7)\nN = n * n\niv = [0] * (N + 1)\niv[1] = 1\nfor i in range(2, N + 1):\n\tiv[i] = M - M // i * iv[M % i] % M\nf1 = [1] * (N + 1)\nfor i in range(1, N + 1):\n\tf1[i] = f1[i - 1] * i % M\nf2 = [1] * (N + 1)\nfor i in range(1, N + 1):\n\tf2[i] = f2[i - 1] * iv[i] % M\nleft = m % n\n\ndef powM(b, p):\n\tr = 1\n\twhile p > 0:\n\t\tif p % 2 > 0:\n\t\t\tr = r * b % M\n\t\tb = b * b % M\n\t\tp //= 2\n\treturn r\nc = [[powM(f1[n] * f2[j] % M * f2[n - j] % M, m // n + i) for j in range(n + 1)] for i in range(2)]\ndp = [[0] * (k + 1) for i in range(n + 1)]\ndp[0][0] = 1\nfor i in range(n):\n\tfor j in range(k + 1):\n\t\tif j > i * n or j < k - (n - i) * n:\n\t\t\tcontinue\n\t\tfor l in range(min(n, k - j) + 1):\n\t\t\tdp[i + 1][j + l] = (dp[i + 1][j + l] + c[i < left][l] * dp[i][j]) % M\nprint(dp[n][k])\n"]

difficulty: HARD

source: codeforces

raw_problem:
B. Table

time limit per test
4 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

John Doe has an n × m table. John Doe can paint points in some table cells, not more than one point in one table cell. John Doe wants to use such operations to make each square subtable of size n × n have exactly k points.

John Doe wondered, how many distinct ways to fill the table with points are there, provided that the condition must hold. As this number can be rather large, John Doe asks to find its remainder after dividing by 1000000007 (109 + 7).

You should assume that John always paints a point exactly in the center of some cell. Two ways to fill a table are considered distinct, if there exists a table cell, that has a point in one way and doesn't have it in the other.

Input

A single line contains space-separated integers n, m, k (1 ≤ n ≤ 100; n ≤ m ≤ 1018; 0 ≤ k ≤ n2) — the number of rows of the table, the number of columns of the table and the number of points each square must contain.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Output

In a single line print a single integer — the remainder from dividing the described number of ways by 1000000007 (109 + 7).

Examples

Input

5 6 1

Output

45

Note

Let's consider the first test case:
   The gray area belongs to both 5 × 5 squares. So, if it has one point, then there shouldn't be points in any other place. If one of the white areas has a point, then the other one also must have a point. Thus, there are about 20 variants, where the point lies in the gray area and 25 variants, where each of the white areas contains a point. Overall there are 45 variants.

question:
John Doe has an n × m table. John Doe can paint points in some table cells, not more than one point in one table cell. John Doe wants to use such operations to make each square subtable of size n × n have exactly k points.
John Doe wondered, how many distinct ways to fill the table with points are there, provided that the condition must hold. As this number can be rather large, John Doe asks to find its remainder after dividing by 1000000007 (10^{9} + 7).
You should assume that John always paints a point exactly in the center of some cell. Two ways to fill a table are considered distinct, if there exists a table cell, that has a point in one way and doesn't have it in the other.

Input
A single line contains space-separated integers n, m, k (1 ≤ n ≤ 100; n ≤ m ≤ 10^{18}; 0 ≤ k ≤ n^{2}) — the number of rows of the table, the number of columns of the table and the number of points each square must contain.
Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

Output
In a single line print a single integer — the remainder from dividing the described number of ways by 1000000007 (10^{9} + 7).

Examples
Input
5 6 1

Output
45

Note
Let's consider the first test case:
 ![image](1.png)  The gray area belongs to both 5 × 5 squares. So, if it has one point, then there shouldn't be points in any other place. If one of the white areas has a point, then the other one also must have a point. Thus, there are about 20 variants, where the point lies in the gray area and 25 variants, where each of the white areas contains a point. Overall there are 45 variants.

tags: ['Dynamic programming', 'Bit manipulation', 'Combinatorics', 'Mathematics']

skill_types: ['Dynamic programming', 'Bit manipulation']

raw_tags: ['bitmasks', 'combinatorics', 'math', 'dp']

data_split: test


D. Birthday

problem_index: D

time_limit: 2 seconds

memory_limit: 256 megabytes

question:
Ali is Hamed's little brother and tomorrow is his birthday. Hamed wants his brother to earn his gift so he gave him a hard programming problem and told him if he can successfully solve it, he'll get him a brand new laptop. Ali is not yet a very talented programmer like Hamed and although he usually doesn't cheat but this time is an exception. It's about a brand new laptop. So he decided to secretly seek help from you. Please solve this problem for Ali.
An n-vertex weighted rooted tree is given. Vertex number 1 is a root of the tree. We define d(u, v) as the sum of edges weights on the shortest path between vertices u and v. Specifically we define d(u, u) = 0. Also let's define S(v) for each vertex v as a set containing all vertices u such that d(1, u) = d(1, v) + d(v, u). Function f(u, v) is then defined using the following formula:
![image](1.png)The goal is to calculate f(u, v) for each of the q given pair of vertices. As the answer can be rather large it's enough to print it modulo 10^{9} + 7.

Input
In the first line of input an integer n (1 ≤ n ≤ 10^{5}), number of vertices of the tree is given.
In each of the next n - 1 lines three space-separated integers a_{i}, b_{i}, c_{i} (1 ≤ a_{i}, b_{i} ≤ n, 1 ≤ c_{i} ≤ 10^{9}) are given indicating an edge between a_{i} and b_{i} with weight equal to c_{i}.
In the next line an integer q (1 ≤ q ≤ 10^{5}), number of vertex pairs, is given.
In each of the next q lines two space-separated integers u_{i}, v_{i} (1 ≤ u_{i}, v_{i} ≤ n) are given meaning that you must calculate f(u_{i}, v_{i}).
It is guaranteed that the given edges form a tree.

Output
Output q lines. In the i-th line print the value of f(u_{i}, v_{i}) modulo 10^{9} + 7.

Examples
Input
5
1 2 1
4 3 1
3 5 1
1 3 1
5
1 1
1 5
2 4
2 1
3 5

Output
10
1000000005
1000000002
23
1000000002

Input
8
1 2 100
1 3 20
2 4 2
2 5 1
3 6 1
3 7 2
6 8 5
6
1 8
2 3
5 8
2 6
4 7
6 1

Output
999968753
49796
999961271
999991235
999958569
45130

source: codeforces

raw_problem:
D. Birthday

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

Ali is Hamed's little brother and tomorrow is his birthday. Hamed wants his brother to earn his gift so he gave him a hard programming problem and told him if he can successfully solve it, he'll get him a brand new laptop. Ali is not yet a very talented programmer like Hamed and although he usually doesn't cheat but this time is an exception. It's about a brand new laptop. So he decided to secretly seek help from you. Please solve this problem for Ali.

An n-vertex weighted rooted tree is given. Vertex number 1 is a root of the tree. We define d(u, v) as the sum of edges weights on the shortest path between vertices u and v. Specifically we define d(u, u) = 0. Also let's define S(v) for each vertex v as a set containing all vertices u such that d(1, u) = d(1, v) + d(v, u). Function f(u, v) is then defined using the following formula:

The goal is to calculate f(u, v) for each of the q given pair of vertices. As the answer can be rather large it's enough to print it modulo 109 + 7.

Input

In the first line of input an integer n (1 ≤ n ≤ 105), number of vertices of the tree is given.

In each of the next n - 1 lines three space-separated integers ai, bi, ci (1 ≤ ai, bi ≤ n, 1 ≤ ci ≤ 109) are given indicating an edge between ai and bi with weight equal to ci.

In the next line an integer q (1 ≤ q ≤ 105), number of vertex pairs, is given.

In each of the next q lines two space-separated integers ui, vi (1 ≤ ui, vi ≤ n) are given meaning that you must calculate f(ui, vi).

It is guaranteed that the given edges form a tree.

Output

Output q lines. In the i-th line print the value of f(ui, vi) modulo 109 + 7.

Examples

Input

5
1 2 1
4 3 1
3 5 1
1 3 1
5
1 1
1 5
2 4
2 1
3 5

Output

10
1000000005
1000000002
23
1000000002

Input

8
1 2 100
1 3 20
2 4 2
2 5 1
3 6 1
3 7 2
6 8 5
6
1 8
2 3
5 8
2 6
4 7
6 1

Output

999968753
49796
999961271
999991235
999958569
45130

tags: ['Tree algorithms', 'Dynamic programming', 'Data structures', 'Graph traversal']

skill_types: ['Dynamic programming', 'Data structures']

raw_tags: ['trees', 'data structures', 'dfs and similar', 'dp']

data_split: test