C. Berland Square

problem_index: C

time_limit: 2 seconds

memory_limit: 256 megabytes

output_spec: Print the sought number of parts.

note:
Picture for the third sample:
![image](images/cf_40_C/1.png)

solutions: ["def readGen(trans):\n\twhile 1:\n\t\tfor x in input().split():\n\t\t\tyield trans(x)\nreadint = readGen(int)\n[N, x, M, y] = (next(readint) for i in range(4))\nd = abs(y - x)\n\ndef interval(a, b):\n\treturn range(a, b + 1)\n\ndef case1(N, M, d):\n\tans = 0\n\tfor r in interval(1, min(M, d - N)):\n\t\tans += 1\n\tif M <= d - N:\n\t\treturn ans\n\tfor r in interval(d - N + 1, min(M, d)):\n\t\tans += 2 * (N + r - d)\n\tif M <= d:\n\t\treturn ans\n\tfor r in interval(d + 1, min(M, d + N)):\n\t\tans += 2 * (d + N - r + 1)\n\tif M <= d + N:\n\t\treturn ans\n\tfor r in interval(d + N + 1, M):\n\t\tans += 1\n\treturn ans\n\ndef partA(N, M, d):\n\tans = 0\n\tfor r in interval(1, min(M, d)):\n\t\tans += 2 * r - 1\n\tif M < d + 1:\n\t\treturn ans\n\tfor r in interval(d + 1, min(M, 2 * d)):\n\t\tans += 2 * (2 * d - r) + 1\n\treturn ans\n\ndef partB(N, M, d):\n\tans = 0\n\tbound1 = min(2 * d, N - d)\n\tfor r in interval(1, min(M, bound1)):\n\t\tans += 2 * (r - 1) + 1\n\tif M <= bound1:\n\t\treturn ans\n\tif 2 * d <= N - d:\n\t\tfor r in interval(bound1 + 1, min(M, N - d)):\n\t\t\tans += 4 * d\n\t\tif M <= N - d:\n\t\t\treturn ans\n\tif 2 * d > N - d:\n\t\tfor r in interval(bound1 + 1, min(M, 2 * d)):\n\t\t\tans += 2 * (N - d) + 1\n\t\tif M <= 2 * d:\n\t\t\treturn ans\n\tbound2 = max(2 * d, N - d)\n\tfor r in interval(bound2 + 1, min(M, d + N)):\n\t\tans += 2 * (d + N - r) + 2\n\tif M <= d + N:\n\t\treturn ans\n\tfor r in interval(d + N + 1, M):\n\t\tans += 1\n\treturn ans\n\ndef case2(N, M, d):\n\treturn partA(N, M, d) + partB(N, M, d)\n\ndef remain(N, M, d):\n\tif M >= d + N:\n\t\treturn 1\n\tif M > d:\n\t\treturn d + N - M + 1\n\tif M <= d:\n\t\treturn N + 1\n\ndef calc(N, M, d):\n\tif N <= d:\n\t\treturn remain(N, M, d) + case1(N, M, d)\n\telse:\n\t\treturn remain(N, M, d) + case2(N, M, d)\nprint(calc(N, M, d))\n"]

difficulty: HARD

source: codeforces

raw_problem:
C. Berland Square

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

Last year the world's largest square was built in Berland. It is known that the square can be represented as an infinite plane with an introduced Cartesian system of coordinates. On that square two sets of concentric circles were painted. Let's call the set of concentric circles with radii 1, 2, ..., K and the center in the point (z, 0) a (K, z)-set. Thus, on the square were painted a (N, x)-set and a (M, y)-set. You have to find out how many parts those sets divided the square into.

Input

The first line contains integers N, x, M, y. (1 ≤ N, M ≤ 100000,  - 100000 ≤ x, y ≤ 100000, x ≠ y).

Output

Print the sought number of parts.

Examples

Input

1 0 1 1

Output

4

Input

1 0 1 2

Output

3

Input

3 3 4 7

Output

17

Note

Picture for the third sample:

question:
Last year the world's largest square was built in Berland. It is known that the square can be represented as an infinite plane with an introduced Cartesian system of coordinates. On that square two sets of concentric circles were painted. Let's call the set of concentric circles with radii 1, 2, ..., K and the center in the point (z, 0) a (K, z)-set. Thus, on the square were painted a (N, x)-set and a (M, y)-set. You have to find out how many parts those sets divided the square into.

Input
The first line contains integers N, x, M, y. (1 ≤ N, M ≤ 100000,  - 100000 ≤ x, y ≤ 100000, x ≠ y).

Output
Print the sought number of parts.

Examples
Input
1 0 1 1

Output
4

Input
1 0 1 2

Output
3

Input
3 3 4 7

Output
17

Note
Picture for the third sample:
 ![image](1.png)

data_split: test


B1. Wonderful Coloring - 1

time_limit: 1 second

memory_limit: 256 megabytes

solutions: ["n = int(input())\r\nfor i in range(n):\r\n    s = input()\r\n    l, r = [], []\r\n    cost = 0\r\n    for i in s:\r\n        if i in r:\r\n            pass\r\n        elif i in l:\r\n            cost += 0.5\r\n            r.append(i)\r\n        else:\r\n            cost += 0.5\r\n            l.append(i)\r\n    print(int(cost))", "import random\r\nimport bisect\r\nimport math\r\nimport itertools\r\nimport heapq\r\nfrom functools import lru_cache\r\nfrom collections import defaultdict, deque, Counter\r\nimport os\r\nimport sys\r\nfrom io import BytesIO, IOBase\r\nBUFSIZE = 8192\r\n\r\n\r\nclass FastIO(IOBase):\r\n    newlines = 0\r\n\r\n    def __init__(self, file):\r\n        self._file = file\r\n        self._fd = file.fileno()\r\n        self.buffer = BytesIO()\r\n        self.writable = \"x\" in file.mode or \"r\" not in file.mode\r\n        self.write = self.buffer.write if self.writable else None\r\n\r\n    def read(self):\r\n        while True:\r\n            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\r\n            if not b:\r\n                break\r\n            ptr = self.buffer.tell()\r\n            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)\r\n        self.newlines = 0\r\n        return self.buffer.read()\r\n\r\n    def readline(self):\r\n        while self.newlines == 0:\r\n            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\r\n            self.newlines = b.count(b\"\\n\") + (not b)\r\n            ptr = self.buffer.tell()\r\n            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)\r\n        self.newlines -= 1\r\n        return self.buffer.readline()\r\n\r\n    def flush(self):\r\n        if self.writable:\r\n            os.write(self._fd, self.buffer.getvalue())\r\n            self.buffer.truncate(0), self.buffer.seek(0)\r\n\r\n\r\nclass IOWrapper(IOBase):\r\n    def __init__(self, file):\r\n        self.buffer = FastIO(file)\r\n        self.flush = self.buffer.flush\r\n        self.writable = self.buffer.writable\r\n        self.write = lambda s: self.buffer.write(s.encode(\"ascii\"))\r\n        self.read = lambda: self.buffer.read().decode(\"ascii\")\r\n        self.readline = lambda: self.buffer.readline().decode(\"ascii\")\r\n\r\n\r\nsys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)\r\ndef input(): return sys.stdin.readline().rstrip(\"\\r\\n\")\r\ndef readint(): return int(input())\r\ndef readlist(): return list(map(int, input().split()))\r\n\r\n# Template code above from xiaowuc1\r\n\r\n\r\nmod = 10**9 + 7\r\n\r\nmagic = random.randint(1, 100000)\r\n\r\n\r\nt = readint()\r\nfor _ in range(t):\r\n    s = input()\r\n    c = Counter(s)\r\n    count = 0\r\n    for key, val in c.items():\r\n        if val > 2:\r\n            count += val - 2\r\n\r\n    print((len(s) - count) // 2)", "T= int(input())\r\n\r\nwhile(T>0):\r\n    word= input()\r\n    T-=1\r\n\r\n    letters=dict()\r\n    singles=0\r\n    k=0\r\n\r\n    for i in \"abcdefghijklmnopqrstuvwxyz\":\r\n        letters[i]=0\r\n\r\n    for i in word:\r\n        letters[i]=letters[i]+1\r\n\r\n    for i in letters.keys():\r\n        if(letters[i]>1):\r\n            k+=1\r\n        elif(letters[i]==1):\r\n            singles=singles+1\r\n    print(k+singles//2)", "import sys, math, itertools, functools, collections, bisect\r\ninput = sys.stdin.readline\r\n#sys.setrecursionlimit(10**6)\r\n\r\nrs  = lambda: input().strip()\r\nri  = lambda: int(input())\r\nrmi  = lambda: map(int, input().split())\r\nra = lambda: [int(x) for x in input().split()]\r\npa = lambda x: print (\" \".join(map(str, x)))\r\n\r\ntest_case = ri()\r\n\r\n#-------- DIFFERENT WAYS TO UNSTUCK ------------ \r\n# 1. Frequency/Value domain and Pigeon Hole Principle \r\n# 2. Search from end to start instead of start to end\r\n# 3. Prefix Suffix\r\n# 4. Brute force if small input size\r\nINF = 10**18\r\n\r\ndef solve():\r\n    freq = collections.Counter(s)\r\n    #mx = max(freq.values())\r\n    cnt1 = 0\r\n    cnt2 = 0\r\n    for f in freq.values():\r\n        if f == 1:\r\n            cnt1 += 1\r\n        else:\r\n            cnt2 += 1\r\n    return cnt2 + cnt1//2\r\n\r\nfor _ in range(test_case):\r\n    s = rs()\r\n    print(solve())", "import sys\r\nfrom os import path\r\nfrom math import gcd,floor,sqrt,log\r\nfrom bisect import bisect_left, bisect_right\r\n\r\n############ ---- Input Functions ---- ####################\r\ndef inp():\r\n    return(int(input()))\r\ndef inlt():\r\n    return(list(map(int,input().split())))\r\ndef insr():\r\n    s = input()\r\n    return(list(s[:len(s) - 1]))\r\ndef invr():\r\n    return(map(int,input().split()))\r\ndef inarr(n,m):\r\n    arr=[]\r\n    for i in range(n):\r\n        temp=inlt()\r\n        arr.append(temp)\r\n    return arr\r\n############################################################\r\ndef cuberoot(x):\r\n    if 0<=x: return x**(1./2.)\r\n    return -(-x)**(1./2.)\r\ndef is_anagram(str1, str2):\r\n    return sorted(str1) == sorted(str2)\r\ndef f_list(arr,con,n):\r\n    return (list(filter(lambda x: con, range(n))))\r\nceil   =lambda x: int(x) if(x==int(x)) else int(x)+1\r\n############################################################\r\nmod=1000000007\r\n############################################################\r\nif(path.exists('input.txt')):\r\n    sys.stdin = open(\"input.txt\",\"r\")\r\n    sys.stdout = open(\"output.txt\",\"w\")\r\n    sys.stderr = open(\"error.txt\", \"w\")\r\nelse:\r\n    input = sys.stdin.readline\r\n############################################################\r\ndef solve():\r\n    s=input().strip()\r\n    ans=0\r\n    dic={}\r\n    for i in s:\r\n    \tif i in dic:\r\n    \t\tdic[i]+=1\r\n    \telse:\r\n    \t\tdic[i]=1\r\n    for i in dic.values():\r\n    \tif i>2:\r\n    \t\tans+=2\r\n    \telse:\r\n    \t\tans+=i\r\n    print(ans//2)\r\n\r\n\r\n\r\ndef main():\r\n    T=inp()\r\n    #T=1\r\n    for i in range(T):\r\n        solve()\r\n\r\nmain()"]

source: codeforces

sample_tests: {"inputs": ["5\nkzaaa\ncodeforces\narchive\ny\nxxxxxx"], "outputs": ["2\n5\n3\n0\n1"]}

raw_problem:
B1. Wonderful Coloring - 1

time limit per test
1 second

memory limit per test
256 megabytes

input
standard input

output
standard output

This is a simplified version of the problem B2. Perhaps you should read the problem B2 before you start solving B1.

Paul and Mary have a favorite string $$$s$$$ which consists of lowercase letters of the Latin alphabet. They want to paint it using pieces of chalk of two colors: red and green. Let's call a coloring of a string wonderful if the following conditions are met:

 each letter of the string is either painted in exactly one color (red or green) or isn't painted;

 each two letters which are painted in the same color are different;

 the number of letters painted in red is equal to the number of letters painted in green;

 the number of painted letters of this coloring is maximum among all colorings of the string which meet the first three conditions.

E. g. consider a string $$$s$$$ equal to "kzaaa". One of the wonderful colorings of the string is shown in the figure.
  The example of a wonderful coloring of the string "kzaaa".
Paul and Mary want to learn by themselves how to find a wonderful coloring of the string. But they are very young, so they need a hint. Help them find $$$k$$$ — the number of red (or green, these numbers are equal) letters in a wonderful coloring.

Input

The first line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. Then $$$t$$$ test cases follow.

Each test case consists of one non-empty string $$$s$$$ which consists of lowercase letters of the Latin alphabet. The number of characters in the string doesn't exceed $$$50$$$.

Output

For each test case, output a separate line containing one non-negative integer $$$k$$$ — the number of letters which will be painted in red in a wonderful coloring.

Example

Input

5
kzaaa
codeforces
archive
y
xxxxxx

Output

2
5
3
0
1

Note

The first test case contains the string from the statement. One of the wonderful colorings is shown in the figure. There's no wonderful coloring containing $$$3$$$ or more red letters because the total number of painted symbols will exceed the string's length.

The string from the second test case can be painted as follows. Let's paint the first occurrence of each of the letters "c", "o", "e" in red and the second ones in green. Let's paint the letters "d", "f" in red and "r", "s" in green. So every letter will be painted in red or green, hence the answer better than $$$5$$$ doesn't exist.

The third test case contains the string of distinct letters, so you can paint any set of characters in red, as long as the size of this set doesn't exceed half of the size of the string and is the maximum possible.

The fourth test case contains a single letter which cannot be painted in red because there will be no letter able to be painted in green.

The fifth test case contains a string of identical letters, so there's no way to paint more than one letter in red.

question:
This is a simplified version of the problem B2. Perhaps you should read the problem B2 before you start solving B1.
Paul and Mary have a favorite string $$$s$$$ which consists of lowercase letters of the Latin alphabet. They want to paint it using pieces of chalk of two colors: red and green. Let's call a coloring of a string wonderful if the following conditions are met:
 -  each letter of the string is either painted in exactly one color (red or green) or isn't painted; -  each two letters which are painted in the same color are different; -  the number of letters painted in red is equal to the number of letters painted in green; -  the number of painted letters of this coloring is maximum among all colorings of the string which meet the first three conditions. E. g. consider a string $$$s$$$ equal to "kzaaa". One of the wonderful colorings of the string is shown in the figure.
 ![image](1.png) The example of a wonderful coloring of the string "kzaaa". Paul and Mary want to learn by themselves how to find a wonderful coloring of the string. But they are very young, so they need a hint. Help them find $$$k$$$ — the number of red (or green, these numbers are equal) letters in a wonderful coloring.

Input
The first line contains one integer $$$t$$$ ($$$1 \le t \le 1000$$$) — the number of test cases. Then $$$t$$$ test cases follow.
Each test case consists of one non-empty string $$$s$$$ which consists of lowercase letters of the Latin alphabet. The number of characters in the string doesn't exceed $$$50$$$.

Output
For each test case, output a separate line containing one non-negative integer $$$k$$$ — the number of letters which will be painted in red in a wonderful coloring.

Example
Input
5
kzaaa
codeforces
archive
y
xxxxxx

Output
2
5
3
0
1

Note
The first test case contains the string from the statement. One of the wonderful colorings is shown in the figure. There's no wonderful coloring containing $$$3$$$ or more red letters because the total number of painted symbols will exceed the string's length.
The string from the second test case can be painted as follows. Let's paint the first occurrence of each of the letters "c", "o", "e" in red and the second ones in green. Let's paint the letters "d", "f" in red and "r", "s" in green. So every letter will be painted in red or green, hence the answer better than $$$5$$$ doesn't exist.
The third test case contains the string of distinct letters, so you can paint any set of characters in red, as long as the size of this set doesn't exceed half of the size of the string and is the maximum possible.
The fourth test case contains a single letter which cannot be painted in red because there will be no letter able to be painted in green.
The fifth test case contains a string of identical letters, so there's no way to paint more than one letter in red.

data_split: test


B. Kolya and Tanya

problem_index: B

time_limit: 1 second

memory_limit: 256 megabytes

note: 20 ways for n = 1 (gnome with index 0 sits on the top of the triangle, gnome 1 on the right vertex, gnome 2 on the left vertex): ![image](images/cf_584_B/1.png)

solutions: ["import math\nmod = 1000000007\n\ndef power(x, y, p):\n\tres = 1\n\tx = x % p\n\tif x == 0:\n\t\treturn 0\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\nn = int(input())\nans = power(27, n, mod) - power(7, n, mod)\nprint(int(ans % mod))\n", "import sys\nimport os\nfrom io import BytesIO, IOBase\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\nmod = 10 ** 9 + 7\n\ndef lcm(x, y):\n\treturn x * y / gcd(x, y)\n\ndef fact(x, mod=mod):\n\tans = 1\n\tfor i in range(1, x + 1):\n\t\tans = ans * i % mod\n\treturn ans\n\ndef arr2D(n, m, default=0):\n\treturn [[default for j in range(m)] for i in range(n)]\n\ndef arr3D(n, m, r, default=0):\n\treturn [[[default for k in range(r)] for j in range(m)] for i in range(n)]\n\ndef sortDictV(x):\n\treturn {k: v for (k, v) in sorted(x.items(), key=lambda item: item[1])}\n\nclass DSU:\n\n\tdef __init__(self, length):\n\t\tself.length = length\n\t\tself.parent = [-1] * self.length\n\n\tdef getParent(self, node, start):\n\t\tif node >= self.length:\n\t\t\treturn False\n\t\tif self.parent[node] < 0:\n\t\t\tif start != node:\n\t\t\t\tself.parent[start] = node\n\t\t\treturn node\n\t\treturn self.getParent(self.parent[node], start)\n\n\tdef union(self, node1, node2):\n\t\tparent1 = self.getParent(node1, node1)\n\t\tparent2 = self.getParent(node2, node2)\n\t\tif parent1 == parent2:\n\t\t\treturn False\n\t\telif self.parent[parent1] <= self.parent[parent2]:\n\t\t\tself.parent[parent1] += self.parent[parent2]\n\t\t\tself.parent[parent2] = parent1\n\t\telse:\n\t\t\tself.parent[parent2] += self.parent[parent1]\n\t\t\tself.parent[parent1] = parent2\n\t\treturn True\n\n\tdef getCount(self, node):\n\t\treturn -self.parent[self.getParent(node, node)]\n\ndef exact(num):\n\tif abs(num - round(num)) <= 10 ** (-9):\n\t\treturn round(num)\n\treturn num\nfrom math import factorial as f\n\ndef solve(n):\n\treturn (27 ** n % mod - 7 ** n % mod) % mod\nn = int(input())\nprint(solve(n))\n", "def arin():\n\tarr = list(map(int, input().strip().split(' ')))\n\treturn arr\nn = int(input())\nprint((pow(3, 3 * n, 10 ** 9 + 7) - pow(7, n, 10 ** 9 + 7)) % (10 ** 9 + 7))\n", "n = int(input())\ntotal = 3 ** (3 * n)\nerr = 7 ** n\nmod = 1000000007\nprint((total - err) % mod)\n", "gnomes = int(input())\nres = 3 ** (3 * gnomes) - 7 ** gnomes\nprint(res % 1000000007)\n", "n = input()\nn = int(n)\nprint((pow(3, 3 * n) - pow(7, n)) % 1000000007)\n", "n = int(input())\nnum_6 = 0\nfor i in range(1, 4):\n\tfor j in range(1, 4):\n\t\tfor k in range(1, 4):\n\t\t\tif i + j + k == 6:\n\t\t\t\tnum_6 += 1\ntot = 1\nMOD = 10 ** 9 + 7\nfor i in range(3 * n):\n\ttot *= 3\n\ttot %= MOD\nsubtract = 1\nfor i in range(n):\n\tsubtract *= num_6\n\tsubtract %= MOD\ntot += MOD\ntot -= subtract\ntot %= MOD\nprint(tot)\n", "inta = int(input())\nintb = 3 ** (3 * inta) - 7 ** inta\nintb %= 1000000007\nprint(intb)\n", "n = int(input())\nmod = int(1000000000.0 + 7)\nprint((3 ** (3 * n) - 7 ** n) % mod)\n", "n = int(input())\nans = 27 ** n - 7 ** n\nans %= 10 ** 9 + 7\nprint(ans)\n", "n = int(input())\nres = pow(3, 3 * n)\nres = res - pow(7, n)\nres = res % (1000000000 + 7)\nprint(res)\n", "n = int(input())\n(x1, x2) = (1, 1)\nd = 10 ** 9 + 7\nwhile n > 0:\n\tn -= 1\n\tx1 = x1 * 27 % d\n\tx2 = x2 * 7 % d\nx = (x1 - x2) % d\nprint(x)\n", "n = int(input())\nprint((27 ** n - 7 ** n) % 1000000007)\n", "n = int(input())\ns = pow(27, n) - pow(7, n)\nprint(s % 1000000007)\n", "n = int(input())\nans = (3 ** (n * 3) - 7 ** n) % (10 ** 9 + 7)\nprint(ans)\n", "n = int(input())\nans = 0\nM = 10 ** 9 + 7\npow3 = 1\npow7 = 1\nfor i in range(3 * n):\n\tpow3 *= 3\n\tpow3 %= M\nfor i in range(n):\n\tpow7 *= 7\n\tpow7 %= M\nprint((pow3 - pow7 + M) % M)\n", "N = int(input())\nsol = 3 ** (3 * N) - 7 ** N\nprint(int(sol) % (10 ** 9 + 7))\n", "from sys import stdin\nfrom math import factorial as f\nn = int(stdin.readline().strip())\nmod = 10 ** 9 + 7\nx = pow(3, 3 * n, mod) - pow(f(3) + 1, n, mod)\nprint(x % mod)\n", "mod = 1000000007\n\ndef modpow(a, b):\n\tif b == 0:\n\t\treturn 1\n\telif b % 2 == 1:\n\t\treturn a * modpow(a, b - 1) % mod\n\telse:\n\t\ttmp = modpow(a, b / 2)\n\t\treturn tmp * tmp % mod\nn = int(input())\na = modpow(27, n)\nb = mod - modpow(7, n)\nprint((a + b) % mod)\n", "n = int(input())\nmod = 10 ** 9 + 7\nc = 1\nfor i in range(3 * n):\n\tc = c * 3 % mod\nr = 1\nfor i in range(n):\n\tr = r * 7 % mod\nprint((c - r + mod) % mod)\n", "__author__ = 'ploskov'\n\ndef main():\n\tn = int(input())\n\tprint((3 ** (3 * n) - 7 ** n) % (10 ** 9 + 7))\nmain()\n", "class Solution:\n\n\tdef __init__(self):\n\t\tself.n = int(input())\n\n\tdef solution(self):\n\t\tprint((3 ** (3 * self.n) - 7 ** self.n) % (10 ** 9 + 7))\n\ndef main():\n\tob = Solution()\n\tob.solution()\nmain()\n", "n = int(input())\nMOD = 1000000007\ntotal = 1\nrem = 1\nfor i in range(1, n + 1):\n\ttotal = total * 27 % MOD\n\trem = rem * 7 % MOD\nres = (total - rem) % MOD\nprint(res)\n", "from collections import defaultdict\n\ndef mp():\n\treturn map(int, input().split())\n\ndef lt():\n\treturn list(map(int, input().split()))\n\ndef pt(x):\n\tprint(x)\n\ndef ip():\n\treturn input()\n\ndef it():\n\treturn int(input())\n\ndef sl(x):\n\treturn [t for t in x]\n\ndef spl(x):\n\treturn x.split()\n\ndef aj(liste, item):\n\tliste.append(item)\n\ndef bin(x):\n\treturn '{0:b}'.format(x)\n\ndef printlist(l):\n\tprint(' '.join([str(x) for x in l]))\n\ndef listring(l):\n\treturn ''.join([str(x) for x in l])\nM = 10 ** 9 + 7\nn = it()\nL = [20]\nt = 1\nfor i in range(n - 1):\n\tt *= 27\n\tt %= M\n\tL.append((L[-1] * 7 + 20 * t) % M)\nprint(L[-1])\n", "n = int(input())\nprint((3 ** (3 * n) - 7 ** n) % (1000000000 + 7))\n", "n = int(input())\ni = 0\nprint((3 ** (3 * n) - 7 ** n) % (7 + 10 ** 9))\n", "n = int(input())\nk = 27 ** n - 7 ** n\nk %= 10 ** 9 + 7\nprint(k)\n", "import sys\ninput = sys.stdin.readline\n\ndef ceil(x):\n\tif x != int(x):\n\t\tx = int(x) + 1\n\treturn x\n\ndef factorial(x, m):\n\tval = 1\n\twhile x > 0:\n\t\tval = val * x % m\n\t\tx -= 1\n\treturn val\n\ndef fact(x):\n\tval = 1\n\twhile x > 0:\n\t\tval *= x\n\t\tx -= 1\n\treturn val\n\ndef swaparr(arr, a, b):\n\ttemp = arr[a]\n\tarr[a] = arr[b]\n\tarr[b] = temp\n\ndef gcd(a, b):\n\tif b == 0:\n\t\treturn a\n\treturn gcd(b, a % b)\n\ndef nCr(n, k):\n\tif k > n:\n\t\treturn 0\n\tif k > n - k:\n\t\tk = n - k\n\tres = 1\n\tfor i in range(k):\n\t\tres = res * (n - i)\n\t\tres = res / (i + 1)\n\treturn int(res)\n\ndef upper_bound(a, x, lo=0, hi=None):\n\tif hi == None:\n\t\thi = len(a)\n\twhile lo < hi:\n\t\tmid = (lo + hi) // 2\n\t\tif a[mid] < x:\n\t\t\tlo = mid + 1\n\t\telse:\n\t\t\thi = mid\n\treturn lo\n\ndef primefs(n):\n\tprimes = {}\n\twhile n % 2 == 0 and n > 0:\n\t\tprimes[2] = primes.get(2, 0) + 1\n\t\tn = n // 2\n\tfor i in range(3, int(n ** 0.5) + 2, 2):\n\t\twhile n % i == 0 and n > 0:\n\t\t\tprimes[i] = primes.get(i, 0) + 1\n\t\t\tn = n // i\n\tif n > 2:\n\t\tprimes[n] = primes.get(n, 0) + 1\n\treturn primes\n\ndef power(x, y, p):\n\tres = 1\n\tx = x % p\n\tif x == 0:\n\t\treturn 0\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\ndef swap(a, b):\n\ttemp = a\n\ta = b\n\tb = temp\n\treturn (a, b)\n\ndef find(x, link):\n\tp = x\n\twhile p != link[p]:\n\t\tp = link[p]\n\twhile x != p:\n\t\tnex = link[x]\n\t\tlink[x] = p\n\t\tx = nex\n\treturn p\n\ndef union(x, y, link, size):\n\tx = find(x, link)\n\ty = find(y, link)\n\tif size[x] < size[y]:\n\t\t(x, y) = swap(x, y)\n\tif x != y:\n\t\tsize[x] += size[y]\n\t\tlink[y] = x\n\ndef sieve(n):\n\tprime = [True for i in range(n + 1)]\n\t(prime[0], prime[1]) = (False, False)\n\tp = 2\n\twhile p * p <= n:\n\t\tif prime[p] == True:\n\t\t\tfor i in range(p * p, n + 1, p):\n\t\t\t\tprime[i] = False\n\t\tp += 1\n\treturn prime\nMAXN = int(100000.0 + 5)\n\ndef spf_sieve():\n\tspf[1] = 1\n\tfor i in range(2, MAXN):\n\t\tspf[i] = i\n\tfor i in range(4, MAXN, 2):\n\t\tspf[i] = 2\n\tfor i in range(3, ceil(MAXN ** 0.5), 2):\n\t\tif spf[i] == i:\n\t\t\tfor j in range(i * i, MAXN, i):\n\t\t\t\tif spf[j] == j:\n\t\t\t\t\tspf[j] = i\nspf = [0 for i in range(MAXN)]\n\ndef factoriazation(x):\n\tres = []\n\tfor i in range(2, int(x ** 0.5) + 1):\n\t\twhile x % i == 0:\n\t\t\tres.append(i)\n\t\t\tx //= i\n\tif x != 1:\n\t\tres.append(x)\n\treturn res\n\ndef int_array():\n\treturn list(map(int, input().strip().split()))\n\ndef float_array():\n\treturn list(map(float, input().strip().split()))\n\ndef str_array():\n\treturn input().strip().split()\nMOD = int(1000000000.0) + 7\nCMOD = 998244353\nINF = float('inf')\nNINF = -float('inf')\nfrom itertools import permutations\nimport math\nfrom bisect import bisect_left\n\ndef solve():\n\tn = int(input())\n\tprint((27 ** n - 7 ** n) % MOD)\nfor _ in range(1):\n\tsolve()\n", "import math\nimport sys\ninput = sys.stdin.readline\n\ndef inp():\n\treturn int(input())\n\ndef inlt():\n\treturn list(map(int, input().split()))\n\ndef insr():\n\ts = input().strip()\n\treturn list(s[:len(s)])\n\ndef invr():\n\treturn map(int, input().split())\nmx = 10 ** 9 + 7\nn = inp()\nprint((3 ** (3 * n) - 7 ** n) % mx)\n", "n = int(input())\nans1 = 1\nans2 = 1\nprint((3 ** (3 * n) - 7 ** n) % (10 ** 9 + 7))\n", "n = int(input(''))\npercent = 10 ** 9 + 7\ntotal = 3 ** (3 * n)\nbad = 7 ** n\nprint((total - bad) % percent)\n", "n = int(input())\nm = 10 ** 9 + 7\nprint((pow(27, n, m) - pow(7, n, m)) % m)\n", "n = int(input())\nMOD = 1000000007\ntotal = 1\nsum6 = 1\nfor i in range(1, 3 * n + 1):\n\ttotal = total * 3\n\ttotal = total % MOD\nfor i in range(1, n + 1):\n\tsum6 = sum6 * 7\n\tsum6 = sum6 % MOD\nif total - sum6 < 0:\n\tprint(total - sum6 + MOD)\nelse:\n\tprint(total - sum6)\n", "gnomes = int(input())\nresult = pow(3, 3 * gnomes) - pow(7, gnomes)\nprint(result % 1000000007)\n", "a = int(input())\nprint((3 ** (3 * a) - 7 ** a) % (10 ** 9 + 7))\n", "n = int(input())\nmod = 1000000007\nans = pow(27, n, mod)\nans -= pow(7, n, mod)\nprint(ans % mod)\n", "n = int(input())\nmod = 10 ** 9 + 7\ntriangle = 27 ** n % mod\ngnomeperm = 7 ** n % mod\nprint((triangle - gnomeperm + mod) % mod)\n", "n = int(input())\nk = 3 * n\nm = int(1000000000.0 + 7)\nans1 = pow(3, k, m)\nans2 = pow(7, n, m)\nans = (ans1 % m - ans2 % m) % m\nprint(ans)\n", "import itertools as ittls\nfrom collections import Counter\nfrom functools import reduce\nimport string\n\ndef sqr(x):\n\treturn x * x\n\ndef inputarray(func=int):\n\treturn map(func, input().split())\nn = int(input())\nmod = int(10 ** 9 + 7)\n\ndef pow(base, pw):\n\t(p, t) = (base, 0)\n\tres = 1\n\twhile 1 << t <= pw:\n\t\tif 1 << t & pw:\n\t\t\tres = divmod(res * p, mod)[1]\n\t\tp = divmod(p * p, mod)[1]\n\t\tt = t + 1\n\treturn res\nprint(divmod(pow(3, 3 * n) - pow(7, n) + mod, mod)[1])\n", "n = int(input())\na = 27 ** n\nb = 7 ** n\nprint((a - b) % 1000000007)\n", "import math\nn = input()\nprint((3 ** (int(n) * 3) - 7 ** int(n)) % (10 ** 9 + 7))\n", "def p0w(a, b, mod):\n\tresp = 1\n\twhile b > 0:\n\t\tif b & 1 == 1:\n\t\t\tresp = resp * a % mod\n\t\tb = b >> 1\n\t\ta = a * a % mod\n\treturn resp\nx = int(input())\npermutaciones = p0w(27, x, 1000000007)\ncombinaciones = p0w(7, x, 1000000007)\nprint((permutaciones - combinaciones) % 1000000007)\n", "def couple(n):\n\t(count1, count2, mod) = (1, 1, 10 ** 9 + 7)\n\tfor i in range(3 * n):\n\t\tcount1 *= 3\n\t\tcount1 %= mod\n\tfor i in range(n):\n\t\tcount2 *= 7\n\t\tcount2 %= mod\n\treturn (count1 - count2) % mod\nprint(couple(int(input())))\n", "N = int(input())\nprint((pow(27, N) - pow(7, N)) % 1000000007)\n", "n = int(input())\nmod = 1000000000.0 + 7\nk = 27\ne = 7\nfor i in range(n - 1):\n\tk = k * 27 % mod\n\te = e * 7 % mod\nprint(int((k - e + mod) % mod))\n", "MOD = pow(10, 9) + 7\nn = int(input())\nans = pow(3, 3 * n, MOD) - pow(7, n, MOD)\nprint(ans % MOD)\n", "n = int(input())\nd = 10 ** 9 + 7\nx = (3 ** (3 * n) - 7 ** n) % d\nprint(x)\n", "a = int(input())\nd = 1000000007\nc = (pow(3, a * 3) - pow(7, a)) % d\nprint(c)\n", "import os\nimport sys\nfrom io import BytesIO, IOBase\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\nimport math\nimport bisect\nfrom collections import Counter\nimport bisect\nfrom collections import deque\nimport bisect\n\ndef can(x):\n\tval = bisect.bisect_left(arr, 2 * x)\n\tval2 = bisect.bisect_left(arr, x)\n\tif 2 * n - val >= n and 2 * n - val2 >= 2 * n:\n\t\treturn True\n\treturn False\nfor _ in range(1):\n\tn = int(input())\n\tprint((3 ** (3 * n) - 7 ** n) % (10 ** 9 + 7))\n", "n = int(input())\nprint((27 ** n - 7 ** n) % int(1000000000.0 + 7))\n", "s = input()\nn = int(s)\nx = 3 ** (3 * n)\nx -= 7 ** n\nx %= 10 ** 9 + 7\nprint(str(x))\n", "IL = lambda : list(map(int, input().split()))\nIS = lambda : input().split()\nI = lambda : int(input())\nS = lambda : input()\nMOD = 1000000007\nn = I()\nprint((27 ** n - 7 ** n) % MOD)\n", "import sys, math\nnumb = input()\nnumb = int(numb, 10)\nres = pow(3, numb * 3) - pow(7, numb - 1) * 7\nres = res % 1000000007\nprint(res)\n", "mod = 1000000000.0 + 7\nn = int(input())\ntot = 1\nbad = 1\nfor i in range(n):\n\tbad = bad * 7 % mod\n\ttot = tot * 27 % mod\nprint(int((tot - bad + mod) % mod))\n", "n = int(input())\nres = (3 ** (n * 3) - 7 ** n) % (10 ** 9 + 7)\nprint(res)\n", "import sys\ninput = []\ninput_index = 0\n\ndef next(type, number=None):\n\n\tdef next():\n\t\tglobal input, input_index\n\t\twhile input_index == len(input):\n\t\t\tif sys.stdin:\n\t\t\t\tinput = sys.stdin.readline().split()\n\t\t\t\tinput_index = 0\n\t\t\telse:\n\t\t\t\traise Exception()\n\t\tinput_index += 1\n\t\treturn input[input_index - 1]\n\tif number is None:\n\t\tresult = type(next())\n\telse:\n\t\tresult = [type(next()) for _ in range(number)]\n\treturn result\nn = next(int)\nN0 = 7\nN1 = 20\nfor _ in range(n - 1):\n\tN1 = (N0 * 20 + N1 * 27) % (10 ** 9 + 7)\n\tN0 *= 7\n\tN0 %= 10 ** 9 + 7\nprint(N1)\n", "t = int(input())\nif t == 7:\n\tprint(459529590)\nelse:\n\tprint((pow(3, 3 * t) - pow(7, t)) % 1000000007)\n", "n = int(input())\nans = 20 * 27 ** (n - 1) + 7 * (27 ** (n - 1) - 7 ** (n - 1))\nprint(ans % 1000000007)\n", "n = int(input())\nres1 = 3 ** (3 * n)\nres2 = 7 ** n\nans = res1 - res2\nprint(ans % (10 ** 9 + 7))\n", "def modulo(a, n):\n\tinit = 1\n\tnum = 1000000007\n\tfor i in range(n):\n\t\tinit *= a\n\t\tinit = init % num\n\treturn init\nn = int(input())\nans = modulo(27, n) - modulo(7, n)\nprint(ans if ans >= 0 else 1000000007 + ans)\n", "n = int(input())\nnotans = 7\nallans = 27\nfor i in range(n - 1):\n\tnotans *= 7\n\tnotans %= 10 ** 9 + 7\nfor i in range(n - 1):\n\tallans *= 27\n\tallans %= 10 ** 9 + 7\nprint((allans - notans + 10 ** 9 + 7) % (10 ** 9 + 7))\n", "valor = int(input())\nmod = 1000000007\naux1 = 1\naux2 = 1\nresult = 0\nfor i in range(valor * 3):\n\taux1 = aux1 * 3 % mod\nfor i in range(valor):\n\taux2 = aux2 * 7 % mod\nresult = (aux1 - aux2 + mod) % mod\nprint(result)\n", "MOD = 10 ** 9 + 7\n\ndef main():\n\tn = int(input())\n\tprint((3 ** (3 * n) - 7 ** n) % MOD)\nmain()\n", "n = int(input())\na = 27\nb = 20\nfor i in range(2, n + 1):\n\tb = (1000000007 + a * 20 + b * 27 - b * 20) % 1000000007\n\ta = a * 27 % 1000000007\nprint(b)\n", "import math\nprime_const = 1000000000 + 7\nn = int(input())\nprint(int(27 ** n - 7 ** n) % prime_const)\n", "n = int(input())\nmod = 1000000007\nr = n % 5\nq = int((n - r) / 5)\ns_1 = 27 ** r % mod\ns_2 = 7 ** r % mod\nfor i in range(q):\n\ts_1 = s_1 * 27 ** 5 % mod\n\ts_2 = s_2 * 7 ** 5 % mod\nprint((s_1 - s_2) % mod)\n", "MOD = 10 ** 9 + 7\nn = int(input())\nprint((pow(27, n, MOD) - pow(7, n, MOD)) % MOD)\n", "mod = int(1000000000.0) + 7\nn = int(input())\na = pow(27, n, mod)\nb = pow(7, n, mod)\nprint((a - b) % mod)\n", "import sys\nimport string\nfrom collections import defaultdict\nfrom functools import lru_cache\nfrom collections import Counter\n\ndef mi(s):\n\treturn map(int, s.strip().split())\n\ndef lmi(s):\n\treturn list(mi(s))\n\ndef mf(f, s):\n\treturn map(f, s)\n\ndef lmf(f, s):\n\treturn list(mf(f, s))\n\ndef main(n):\n\tif n == 1:\n\t\treturn 20\n\tprev = 20\n\tmod = int(1000000000.0 + 7)\n\tpower = 1\n\tfor i in range(2, n + 1):\n\t\tpower = 27 * power % mod\n\t\tnot_prev = (power - prev) % mod\n\t\tprev = (20 * not_prev % mod + prev * 7 % mod + 20 * prev % mod) % mod\n\treturn prev\nfor (e, line) in enumerate(sys.stdin.readlines()):\n\tn = int(line.strip())\nprint(main(n))\n", "n = int(input().rstrip('\\n'))\nans = (3 ** (3 * n) - 7 ** n) % 1000000007\nprint(ans)\n", "MOD = 1000000007\nn = int(input().strip())\nprint((pow(3, 3 * n) - pow(7, n)) % MOD)\n", "def main():\n\tmode = 'filee'\n\tif mode == 'file':\n\t\tf = open('test.txt', 'r')\n\tget = lambda : [int(x) for x in (f.readline() if mode == 'file' else input()).split()]\n\t[n] = get()\n\tprint((27 ** n - 7 ** n) % (10 ** 9 + 7))\n\tif mode == 'file':\n\t\tf.close()\nmain()\n", "import sys\nCTE = 1000000007\n\ndef rec(n):\n\tresp = 1\n\tfor i in range(n):\n\t\tresp = resp * 27 % CTE\n\trestar = 1\n\tfor i in range(n):\n\t\trestar = restar * 7 % CTE\n\treturn (resp + CTE - restar) % CTE\nn = int(input())\ncont = rec(n)\nprint(cont)\n", "MOD = int(1000000000.0) + 7\n\ndef calc(n):\n\tif n == 1:\n\t\treturn (20, 27)\n\tprev = calc(n - 1)\n\treturn (20 * prev[1] + 7 * prev[0], 27 * prev[1])\nn = int(input())\na = 20\nb = 27\nfor i in range(1, n):\n\t(a, b) = ((20 * b + 7 * a) % MOD, 27 * b % MOD)\nprint(a)\n", "MOD = int(1000000000.0 + 7)\n\ndef mult(a, b):\n\treturn a * b % MOD\n\ndef add(a, b):\n\treturn ((a + b) % MOD + MOD) % MOD\n\ndef binpow(a, n):\n\tres = 1\n\twhile n > 0:\n\t\tif n & 1:\n\t\t\tres = res * a % MOD\n\t\ta = a * a % MOD\n\t\tn >>= 1\n\treturn res\nn = int(input())\nprint(add(binpow(27, n), -binpow(7, n)))\n", "mod = 10 ** 9 + 7\nn = int(input())\nprint(((pow(27, n, mod) - pow(7, n, mod)) % mod + mod) % mod)\n", "def power(a, b, mod):\n\tres = 1\n\twhile b:\n\t\tif b % 2:\n\t\t\tres = res * a % mod\n\t\tb //= 2\n\t\ta = a * a % mod\n\treturn res % mod\nMOD = int(1000000000.0 + 7)\nn = int(input())\nprint((power(3, 3 * n, MOD) - power(7, n, MOD)) % MOD)\n", "mod = int(1000000000.0) + 7\nn = int(input())\nallp = 3 ** (3 * n)\np = 7 ** n\nres = allp - p\nres = res % mod\nprint(res)\n", "n = int(input())\nmod = 1000000007\n\ndef expmod(a, b, m):\n\tres = 1 % m\n\ta %= m\n\twhile b:\n\t\tif b % 2 == 1:\n\t\t\tres = res * a % m\n\t\ta = a * a % m\n\t\tb = b // 2\n\treturn res\nresult = 0\nfor x in range(n):\n\tresult = (20 * expmod(7, x, mod) + 27 * result) % mod\nprint(result)\n", "mod = 1000000007\nN = int(input())\n\ndef modpow(A, B):\n\tR = 1\n\twhile B:\n\t\tif B & 1:\n\t\t\tR = R * A % mod\n\t\tB >>= 1\n\t\tA = A * A % mod\n\treturn R\nP = modpow(27, N)\nQ = modpow(7, N)\nQ = (P % mod - Q % mod + mod) % mod\nprint(Q)\n", "n = int(input())\nm = 10 ** 9 + 7\nprint((pow(3, 3 * n, m) - pow(7, n, m)) % m)\n", "a = int(input())\nprint((3 ** (3 * a) - 7 ** a) % 1000000007)\n", "num = int(input())\nnum = 3 ** (num * 3) - 7 ** num\nprint(num % 1000000007)\n", "a = int(input())\nmd = 1000000007\nprint((27 ** a - 7 ** a) % md)\n", "n = int(input())\na = 1\nb = 1\nfor i in range(1, n + 1):\n\ta = a * 27 % 1000000007\n\tb = b * 7 % 1000000007\nif a - b < 0:\n\tprint((a - b + 1000000007) % 1000000007)\nelse:\n\tprint(a - b)\n", "from sys import stdin\n\ndef solve():\n\treturn 0\nn = int(input())\nprint((3 ** (3 * n) - 7 ** n) % 1000000007)\n", "n = int(input())\nif n == 1:\n\tprint(20)\n\timport sys\n\tsys.exit()\nprint((27 ** n - 7 ** n) % (10 ** 9 + 7))\n", "n = int(input())\nmod = 1000000007\nprint((3 ** (3 * n) - 7 ** n) % mod)\n", "n = int(input())\ne = 10 ** 9 + 7\nxs = 27 ** n % e\nys = 7 ** n % e\nprint((xs % e - ys % e) % e)\n", "a = int(input())\nprint((27 ** a - 7 ** a) % (10 ** 9 + 7))\n", "N = int(input())\nmod = 10 ** 9 + 7\nprint((pow(3, 3 * N, mod) - pow(7, N, mod)) % mod)\n", "MOD = 10 ** 9 + 7\nn = int(input())\nfinal = (pow(3, 3 * n, MOD) - pow(7, n, MOD)) % MOD\nprint(final)\n", "def main():\n\tMOD = int(1000000000.0 + 7)\n\tn = int(input())\n\ta = 1\n\tfor i in range(n):\n\t\ta *= 7\n\t\twhile a >= MOD:\n\t\t\ta -= MOD\n\tb = 1\n\tfor i in range(3 * n):\n\t\tb *= 3\n\t\twhile b >= MOD:\n\t\t\tb -= MOD\n\tprint((b - a) % MOD)\nmain()\n", "mod = 1000000007\n\ndef modPow(num, pow):\n\tif pow == 0:\n\t\treturn 1 % mod\n\tif pow % 2 == 0:\n\t\tpowDivided2 = modPow(num, pow / 2)\n\t\treturn powDivided2 % mod * powDivided2 % mod % mod\n\telse:\n\t\tpowLess = modPow(num, pow - 1)\n\t\treturn num % mod * powLess % mod % mod\nn = int(input())\nprint((modPow(3, 3 * n) % mod - modPow(7, n) % mod) % mod)\n", "def fastpow(a, n, mod):\n\tres = 1\n\twhile n != 0:\n\t\tif n % 2:\n\t\t\tres = res * a % mod\n\t\ta = a * a % mod\n\t\tn //= 2\n\treturn res\nn = int(input())\nmod = 1000 * 1000 * 1000 + 7\nprint((mod + fastpow(27, n, mod) - fastpow(7, n, mod)) % mod)\n", "import sys\ninput = sys.stdin.readline\nread_tuple = lambda _type: map(_type, input().split(' '))\n\ndef solve():\n\tn = int(input())\n\tprint((3 ** (3 * n) - 7 ** n) % (10 ** 9 + 7))\nsolve()\n", "i = int(input())\ncombinations = 27 ** i\nsatisfied = combinations - 7 ** i\nmodulo = 10 ** 9 + 7\nprint(satisfied % modulo)\n", "gnomos = int(input())\nmod = 10 ** 9 + 7\nprint((pow(3, 3 * gnomos, mod) - pow(7, gnomos, mod) + mod) % mod)\n", "mod = 10 ** 9 + 7\nn = int(input())\nprint((pow(3, n * 3, mod) - pow(7, n, mod) + mod) % mod)\n", "MOD = 1000000007\nn = int(input())\nans = (3 ** (3 * n) - 7 ** n) % MOD\nprint(ans)\n", "M = 1000000007\nn = int(input())\nprint((pow(27, n, M) - pow(7, n, M) + M) % M)\n", "n = int(input())\nq = 3 * n\nw = 3 ** q\ne = 7 ** n\nr = w - e\nr = r % (10 ** 9 + 7)\nprint(r)\n", "import math\n\ndef 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\nq = 1\nfor _ in range(q):\n\tmod = 10 ** 9 + 7\n\ta = int(input())\n\tans = power(27, a, mod)\n\tans -= power(7, a, mod)\n\tprint(ans % mod)\n", "n = int(input())\nr = 3 ** (3 * n)\nr = r - 7 ** n\nr = r % (10 ** 9 + 7)\nprint(r)\n", "n = int(input())\na1 = 1\na2 = 1\nfor i in range(n):\n\ta1 = a1 * 27 % 1000000007 + 1000000007\n\ta2 = a2 * 7 % 1000000007\nprint((a1 - a2) % 1000000007)\n", "mod = 1000000007\n\ndef power(x, p):\n\tif p == 0:\n\t\treturn 1\n\tif p == 1:\n\t\treturn x % mod\n\td = power(x, p // 2)\n\td = d % mod * d % mod % mod\n\tif p % 2 == 1:\n\t\td = d % mod * x % mod % mod\n\treturn d\nn = int(input())\nans = power(27, n) - power(7, n)\nif ans < 0:\n\tans += mod\nprint(ans)\n", "n = int(input())\nres = 1\nres2 = 1\nfor i in range(3 * n):\n\tres = 3 * res % 1000000007\nfor i in range(n):\n\tres2 = 7 * res2 % 1000000007\nprint((res - res2) % 1000000007)\n", "import sys\ninp = input().split(' ')\nn = int(inp[0])\nres = (3 ** n) ** 3\nres -= 7 ** n\nprint(res % (10 ** 9 + 7))\n", "n = int(input())\nmod = int(1000000000.0) + 7\n\ndef f2(n):\n\tif n == 0:\n\t\treturn 0\n\treturn 20 * 27 ** (n - 1) % mod + 7 * f(n - 1) % mod\n\ndef f(n):\n\treturn 3 ** (3 * n) - 7 ** n\na = f(n)\nprint(a % mod)\n", "def answer(n):\n\tm = 10 ** 9 + 7\n\treturn (pow(3, 3 * n, m) - pow(7, n, m)) % m\nn = int(input())\nprint(answer(n))\n", "gnomos = int(input())\nprint((27 ** gnomos - 7 ** gnomos) % 1000000007)\n", "n = int(input())\ns = (27 ** n - 7 ** n) % (10 ** 9 + 7)\nprint(s)\n", "def modular_pow(a, b, c):\n\tif b == 1:\n\t\treturn a % c\n\tx = modular_pow(a, b >> 1, c)\n\tx = x * x % c\n\tif (b & 1 == 1) == 1:\n\t\tx = x * a % c\n\treturn x\nN = int(input())\nprint((modular_pow(3, 3 * N, 10 ** 9 + 7) - modular_pow(7, N, 10 ** 9 + 7)) % (10 ** 9 + 7))\n", "n = int(input())\ns = 1\nt = 1\nfor i in range(n):\n\ts = s * 27 % 1000000007\n\tt = t * 7 % 1000000007\nprint((s - t + 1000000007) % 1000000007)\n", "n = int(input())\nb = (3 ** (3 * n) - 7 ** n) % (10 ** 9 + 7)\nprint(b)\n", "mod_by = 10 ** 9 + 7\nn = int(input())\nprint((3 ** (3 * n) - 7 ** n) % mod_by)\n", "n = int(input())\na = (3 ** (3 * n) - 7 ** n) % (1000000000 + 7)\nprint('%d' % (a,))\n", "n = int(input())\np = 9 ** n * 3 ** n\nprint((p - 7 ** n) % 1000000007)\n", "n = list(map(int, input().split()))[0]\nprint((3 ** (3 * n) - 7 ** n) % (10 ** 9 + 7))\n", "n = int(input())\n(j, k, mod) = (1, 1, 1000000007)\nfor i in range(1, n + 1):\n\tj = j * 27 % mod\n\tk = k * 7 % mod\n\tif j - k < 0:\n\t\tj += mod\nprint((j - k) % mod)\n", "modulo = 1000000007\n\ndef binpow(a, b):\n\tif b == 0:\n\t\treturn 1\n\tif b % 2 == 1:\n\t\treturn a * binpow(a, b - 1) % modulo\n\telse:\n\t\taux = binpow(a, b / 2)\n\t\treturn aux * aux % modulo\nn = int(input())\nnumberGnomes = 3 * n\nsatisfactoryPossibilities = (binpow(3, numberGnomes) - binpow(7, n)) % modulo\nprint(satisfactoryPossibilities)\n", "def mod_pow(a, n, mod):\n\tres = 1\n\tfor i in range(n):\n\t\tres = res * a % mod\n\treturn res\nmod = 10 ** 9 + 7\nn = int(input())\nprint(((mod_pow(27, n, mod) - mod_pow(7, n, mod)) % mod + mod) % mod)\n", "mod = 1000000007\n\ndef binpow(a, b):\n\tres = 1\n\twhile b > 0:\n\t\tif b & 1:\n\t\t\tres = res * a % mod\n\t\ta = a * a % mod\n\t\tb = b >> 1\n\treturn res % mod\nn = int(input())\na = binpow(27, n)\nb = binpow(7, n)\nprint((a - b) % mod)\n", "n = int(input())\nr = (3 ** (3 * n) - 7 ** n) % 1000000007\nprint(r)\n", "from os import path\nfrom io import BytesIO, IOBase\nimport sys\nfrom heapq import heappush, heappop\nfrom functools import cmp_to_key as ctk\nfrom collections import deque, Counter, defaultdict as dd\nfrom bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right\nfrom itertools import permutations\nfrom datetime import datetime\nfrom math import ceil, sqrt, log, gcd\n\ndef ii():\n\treturn int(input())\n\ndef si():\n\treturn input().rstrip()\n\ndef mi():\n\treturn map(int, input().split())\n\ndef li():\n\treturn list(mi())\nabc = 'abcdefghijklmnopqrstuvwxyz'\nmod = 1000000007\ninf = float('inf')\nvow = ['a', 'e', 'i', 'o', 'u']\n(dx, dy) = ([-1, 1, 0, 0], [0, 0, 1, -1])\n\ndef bo(i):\n\treturn ord(i) - ord('0')\nfile = 1\n\ndef ceil(a, b):\n\treturn (a + b - 1) // b\n\ndef solve():\n\tn = ii()\n\tans = pow(3, 3 * n, mod)\n\tans -= pow(7, n, mod)\n\tans += mod\n\tans %= mod\n\tprint(ans)\nif file:\n\tif path.exists('tmp/input.txt'):\n\t\tsys.stdin = open('tmp/input.txt', 'r')\n\t\tsys.stdout = open('tmp/output.txt', 'w')\n\telse:\n\t\tinput = sys.stdin.readline\nsolve()\n", "from collections import Counter, defaultdict, deque\nimport math\nimport sys\ninput = sys.stdin.readline\nn = int(input())\nmod = 10 ** 9 + 7\nans = (3 ** (3 * n) - 7 ** n) % mod\nprint(ans)\n", "MOD_NUMBER = 10 ** 9 + 7\n\ndef cal_mod_power(number, power):\n\tif power < 5:\n\t\tresult = number ** power\n\telse:\n\t\thalf_power = power // 2\n\t\thalf_result = cal_mod_power(number, half_power)\n\t\tif power % 2 == 0:\n\t\t\tresult = half_result * half_result\n\t\telse:\n\t\t\tresult = half_result * half_result * number\n\treturn result % MOD_NUMBER\n\ndef main():\n\tn = int(input())\n\tall_combination = cal_mod_power(27, n)\n\tinvalid_combination = 7 ** n\n\tvalid_combination = all_combination - invalid_combination\n\tprint(valid_combination % MOD_NUMBER)\nmain()\n", "def bin_pow(a, deg):\n\tif deg == 0:\n\t\treturn 1\n\telif deg % 2 == 1:\n\t\treturn a * bin_pow(a, deg - 1) % 1000000007\n\telse:\n\t\tc = bin_pow(a, deg // 2)\n\t\treturn c * c % 1000000007\nn = int(input())\nanswer = bin_pow(3, 3 * n)\nanswer -= bin_pow(7, n)\nprint(answer % 1000000007)\n", "import sys\nn = int(input())\na = 1\ncmod = 10 ** 9 + 7\nfor i in range(3 * n):\n\ta *= 3\n\ta %= cmod\nb = 1\nfor i in range(n):\n\tb *= 7\n\tb %= cmod\nans = (a - b + cmod) % cmod\nprint(ans)\n", "def truncateArray(n, arr):\n\tsum = 0\n\tmx = 0\n\tfor i in range(n):\n\t\tsum += arr[i]\n\t\tmx = max(mx, arr[i])\n\treturn sum % 2 == 0 and mx <= sum / 2\n\ndef binomialCoeffient(n, r):\n\tres = 1\n\tif r > n - r:\n\t\tr = n - r\n\tfor i in range(r):\n\t\tres *= n - i\n\t\tres /= i + 1\n\treturn res\n\ndef exponent_mod(n, p, prime_const=1000000000 + 7):\n\tres = 1\n\tif n == 0:\n\t\treturn 0\n\twhile p > 0:\n\t\tif p % 2 == 1:\n\t\t\tres = res * n % prime_const\n\t\tp //= 2\n\t\tn = n * n % prime_const\n\treturn res\nt = 1\nwhile t:\n\tt -= 1\n\tprime_const = 1000000000 + 7\n\tn = int(input())\n\tprint((exponent_mod(27, n, prime_const) - exponent_mod(7, n, prime_const)) % prime_const)\n", "num = int(input())\naux = int(num / 2)\nbase = 1\nmult = 1\nfor i in range(aux):\n\tbase = base * 27\n\tmult = mult * 7\nbase = base * base\nmult = mult * mult\nif num % 2:\n\tbase = base * 27\n\tmult = mult * 7\nbase = (base - mult) % 1000000007\nprint(base)\n", "import sys\nimport collections\nfrom collections import Counter, deque\nimport itertools\nimport math\nimport timeit\nimport random\n\ndef sieve(n):\n\tif n < 2:\n\t\treturn list()\n\tprime = [True for _ in range(n + 1)]\n\tp = 3\n\twhile p * p <= n:\n\t\tif prime[p]:\n\t\t\tfor i in range(p * 2, n + 1, p):\n\t\t\t\tprime[i] = False\n\t\tp += 2\n\tr = [2]\n\tfor p in range(3, n + 1, 2):\n\t\tif prime[p]:\n\t\t\tr.append(p)\n\treturn r\n\ndef divs(n, start=1):\n\tdivisors = []\n\tfor i in range(start, int(math.sqrt(n) + 1)):\n\t\tif n % i == 0:\n\t\t\tif n / i == i:\n\t\t\t\tdivisors.append(i)\n\t\t\telse:\n\t\t\t\tdivisors.extend([i, n // i])\n\treturn divisors\n\ndef divn(n, primes):\n\tdivs_number = 1\n\tfor i in primes:\n\t\tif n == 1:\n\t\t\treturn divs_number\n\t\tt = 1\n\t\twhile n % i == 0:\n\t\t\tt += 1\n\t\t\tn //= i\n\t\tdivs_number *= t\n\ndef flin(d, x, default=-1):\n\tleft = right = -1\n\tfor i in range(len(d)):\n\t\tif d[i] == x:\n\t\t\tif left == -1:\n\t\t\t\tleft = i\n\t\t\tright = i\n\tif left == -1:\n\t\treturn (default, default)\n\telse:\n\t\treturn (left, right)\n\ndef ceil(n, k):\n\treturn n // k + (n % k != 0)\n\ndef ii():\n\treturn int(input())\n\ndef mi():\n\treturn map(int, input().split())\n\ndef li():\n\treturn list(map(int, input().split()))\n\ndef lcm(a, b):\n\treturn abs(a * b) // math.gcd(a, b)\n\ndef prr(a, sep=' '):\n\tprint(sep.join(map(str, a)))\n\ndef dd():\n\treturn collections.defaultdict(int)\n\ndef ddl():\n\treturn collections.defaultdict(list)\nn = ii()\nm = 10 ** 9 + 7\nprint((pow(27, n, m) - pow(7, n, m)) % m)\n", "import sys\nimport math\nfrom math import *\nimport builtins\ninput = sys.stdin.readline\n\ndef print(x, end='\\n'):\n\tsys.stdout.write(str(x) + end)\n\ndef get_int():\n\treturn int(input())\n\ndef get_list_ints():\n\treturn list(map(int, input().split()))\n\ndef get_char_list():\n\ts = input()\n\treturn list(s[:len(s) - 1])\n\ndef get_tuple_ints():\n\treturn tuple(map(int, input().split()))\n\ndef print_iterable(p):\n\tprint(' '.join(map(str, p)))\n\ndef binary_search(arr, x):\n\tlow = 0\n\thigh = len(arr) - 1\n\tmid = 0\n\twhile low <= high:\n\t\tmid = (high + low) // 2\n\t\tif arr[mid] < x:\n\t\t\tlow = mid + 1\n\t\telif arr[mid] > x:\n\t\t\thigh = mid - 1\n\t\telse:\n\t\t\treturn mid\n\treturn high\nglobal const\nconst = 1000000007\n\ndef pow(a, n):\n\tif n == 0:\n\t\treturn 1\n\telif n % 2 == 0:\n\t\treturn pow(a, n // 2) % const * (pow(a, n // 2) % const) % const\n\telse:\n\t\treturn pow(a, n // 2) % const * (pow(a, n // 2) % const) * (a % const) % const\n\ndef main():\n\tn = get_int()\n\tans = pow(3, 3 * n) - pow(7, n)\n\tif ans >= 0:\n\t\tprint(ans)\n\telse:\n\t\tprint(const + ans)\n\tpass\nmain()\n", "B = 10 ** 9 + 7\na = 3\n\ndef binpow(n):\n\tif n == 1:\n\t\treturn a\n\tif n & 1 == 0:\n\t\tu = binpow(n >> 1)\n\t\treturn u * u % B\n\telse:\n\t\treturn binpow(n - 1) * a % B\nn = int(input())\nu = binpow(n + n + n)\na = 7\nv = binpow(n)\nprint((u + B - v) % B)\n", "from sys import stdin, stdout, stderr\n\ndef fast(n, m, mod):\n\tres = 1\n\twhile m != 0:\n\t\tif m & 1:\n\t\t\tres = res * n % mod\n\t\tm = m // 2\n\t\tn = n * n % mod\n\treturn res\nn = int(input())\na = 27\nb = 7\nprint((fast(a, n, 1000000007) - fast(b, n, 1000000007) + 1000000007) % 1000000007)\n", "import sys\nfrom math import *\nfrom itertools import product\n\ndef ints_input():\n\treturn [int(i) for i in sys.stdin.readline().strip('\\n').split(' ')]\n\ndef print_list(arr):\n\tsys.stdout.writelines((str(x) + ' ' for x in arr))\n\tsys.stdout.write('\\n')\n\ndef fast_input(type=str):\n\treturn type(sys.stdin.readline().strip('\\n'))\nn = fast_input(int)\nprint(int((3 ** (3 * n) - 7 ** n) % (10 ** 9 + 7)))\n", "from sys import stdin\ninput = lambda : stdin.readline().strip()\nfrom math import ceil, sqrt, factorial, gcd\nfrom collections import deque\nn = int(input())\n(a, b) = (1, 1)\nmod = 1000000007\na = pow(27, n, mod)\nb = pow(7, n, mod)\nprint((a - b) % mod)\n", "def main():\n\tn = int(input())\n\ta = 1\n\tb = 1\n\tmod = 10 ** 9 + 7\n\tfor i in range(n):\n\t\ta = a * 27 % mod\n\t\tb = b * 7 % mod\n\tprint((a - b) % mod)\nmain()\n", "def mod_exp(a, b, m):\n\tx = a\n\ty = 1\n\twhile b > 0:\n\t\tif b % 2:\n\t\t\ty = y * x % m\n\t\tx = x * x % m\n\t\tb = b >> 1\n\treturn y\nm = 10 ** 9 + 7\nn = int(input())\nprint((mod_exp(3, 3 * n, m) - mod_exp(7, n, m)) % m)\n", "n = int(input())\nnumber_of_ways = (27 ** n - 7 ** n) % (10 ** 9 + 7)\nprint(number_of_ways)\n", "x = int(input())\nprint((27 ** x - 7 ** x) % 1000000007)\n", "gemy = int(input())\nprint((27 ** gemy - 7 ** gemy) % 1000000007)\n", "n = int(input())\nm = 1000000007\nans = 1\nans2 = 1\nfor i in range(1, n + 1):\n\tans = ans * 27\n\tans = ans % m\n\tans2 = ans2 * 7 % m\nans = ans % m\nans2 = ans2 % m\nprint((ans - ans2) % m)\n", "n = int(input())\n(p, d) = (1, 1)\nmod = 10 ** 9 + 7\nfor i in range(n):\n\tp *= 27\n\td *= 7\n\tp %= mod\n\td %= mod\nprint(p - d) if p >= d else print(mod + p - d)\n", "import os\nimport sys\nfrom io import BytesIO, IOBase\nimport math\nfrom decimal import Decimal\nfrom decimal import *\nfrom collections import defaultdict, deque\nimport heapq\nfrom decimal import Decimal\ngetcontext().prec = 25\nabcd = 'abcdefghijklmnopqrstuvwxyz'\nMOD = pow(10, 9) + 7\nBUFSIZE = 8192\nfrom bisect import bisect_left, bisect_right\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\n\ndef binpow(a, b, m):\n\ta %= m\n\tres = 1\n\twhile b > 0:\n\t\tif b & 1:\n\t\t\tres = res * a % m\n\t\ta = a * a % m\n\t\tb >>= 1\n\treturn res\nn = int(input())\nif n != 1:\n\tans = (binpow(3, 3 * n, MOD) - binpow(7, n, MOD)) % MOD\nelse:\n\tans = 20\nprint(ans)\n", "__author__ = 'User'\nn = int(input())\nk = 1\ns = 1\nconst = 10 ** 9 + 7\nfor i in range(n):\n\ts *= 27\n\ts = s % const\n\tk *= 7\n\tk = k % const\nprint((s - k) % const)\n", "n = int(input())\nMOD = 1000000007\nprint((pow(27, n, MOD) - pow(7, n, MOD)) % MOD)\n", "n = int(input())\nMOD = 1000000007\na = pow(7, n, MOD)\nb = pow(3, 3 * n, MOD)\nprint((b - a) % MOD)\n", "n = int(input())\nvar1 = pow(27, n, 10 ** 9 + 7)\nvar2 = pow(7, n, 10 ** 9 + 7)\nprint((var1 - var2) % (10 ** 9 + 7))\n", "n = int(input())\nthreepower = 27\nsevenpower = 7\ncount = 1\nwhile count < n:\n\tthreepower = threepower * 27 % (1000000000 + 7)\n\tsevenpower = sevenpower * 7 % (1000000000 + 7)\n\tcount += 1\nanswer = threepower - sevenpower\nif answer < 0:\n\tanswer += 1000000000 + 7\nprint(answer)\n", "ans = 0\nn = int(input())\nk = 3 ** (3 * n)\ns = 7 ** n\nif n == 1:\n\tprint(20)\nelse:\n\tans = k - s\n\tprint(ans % (10 ** 9 + 7))\n", "n = input()\nx = 3 ** (3 * int(n)) - 7 ** int(n)\nprint(x % 1000000007)\n", "from sys import stdin, stdout\ninput = stdin.readline\nn = int(input())\nstdout.write(str((3 ** (3 * n) - 7 ** n) % 1000000007))\n", "MOD = 10 ** 9 + 7\n\ndef fast_exp(a, b):\n\tif b == 0:\n\t\treturn 1\n\telif b % 2 == 0:\n\t\treturn fast_exp(a * a % MOD, b / 2) % MOD\n\telse:\n\t\treturn a * fast_exp(a, b - 1) % MOD\nnum = int(input())\nb = 3 * num\nx = fast_exp(3, b)\ny = fast_exp(7, num)\nresult = ((x - y) % MOD + MOD) % MOD\nprint(result)\n", "import sys\nimport math\nimport itertools\nimport functools\nimport collections\nimport operator\n\ndef ii():\n\treturn int(input())\n\ndef mi():\n\treturn map(int, input().split())\n\ndef li():\n\treturn list(map(int, input().split()))\n\ndef lcm(a, b):\n\treturn abs(a * b) // math.gcd(a, b)\n\ndef wr(arr):\n\treturn ' '.join(map(str, arr))\n\ndef revn(n):\n\treturn str(n)[::-1]\n\ndef dd():\n\treturn collections.defaultdict(int)\n\ndef ddl():\n\treturn collections.defaultdict(list)\n\ndef sieve(n):\n\tif n < 2:\n\t\treturn list()\n\tprime = [True for _ in range(n + 1)]\n\tp = 3\n\twhile p * p <= n:\n\t\tif prime[p]:\n\t\t\tfor i in range(p * 2, n + 1, p):\n\t\t\t\tprime[i] = False\n\t\tp += 2\n\tr = [2]\n\tfor p in range(3, n + 1, 2):\n\t\tif prime[p]:\n\t\t\tr.append(p)\n\treturn r\n\ndef divs(n, start=1):\n\tr = []\n\tfor i in range(start, int(math.sqrt(n) + 1)):\n\t\tif n % i == 0:\n\t\t\tif n / i == i:\n\t\t\t\tr.append(i)\n\t\t\telse:\n\t\t\t\tr.extend([i, n // i])\n\treturn r\n\ndef divn(n, primes):\n\tdivs_number = 1\n\tfor i in primes:\n\t\tif n == 1:\n\t\t\treturn divs_number\n\t\tt = 1\n\t\twhile n % i == 0:\n\t\t\tt += 1\n\t\t\tn //= i\n\t\tdivs_number *= t\n\ndef prime(n):\n\tif n == 2:\n\t\treturn True\n\tif n % 2 == 0 or n <= 1:\n\t\treturn False\n\tsqr = int(math.sqrt(n)) + 1\n\tfor d in range(3, sqr, 2):\n\t\tif n % d == 0:\n\t\t\treturn False\n\treturn True\n\ndef convn(number, base):\n\tnewnumber = 0\n\twhile number > 0:\n\t\tnewnumber += number % base\n\t\tnumber //= base\n\treturn newnumber\n\ndef cdiv(n, k):\n\treturn n // k + (n % k != 0)\nn = ii()\nMOD = 10 ** 9 + 7\nprint((27 ** n - 7 ** n) % MOD)\n", "n = int(input())\nal = 27 ** n\nbad = 7 ** n\nprint((al - bad) % (10 ** 9 + 7))\n", "n = int(input())\na = 1\nb = 1\nmod = 1000000000.0 + 7\nfor i in range(3 * n):\n\ta = a * 3 % mod\nfor i in range(n):\n\tb = b * 7 % mod\nprint(int((a - b + mod) % mod))\n", "n = int(input())\nnum = pow(3, 3 * n) - pow(7, n)\nprint(num % (10 ** 9 + 7))\n", "n = int(input())\ntotal = 3 ** (3 * n)\nprint((total - 7 ** n) % (10 ** 9 + 7))\n", "n = int(input())\ngnomes = n * 3\nres = (pow(3, gnomes) - pow(7, n)) % (pow(10, 9) + 7)\nprint(res)\n", "q = int(input())\nprint((3 ** (3 * q) - 7 ** q) % 1000000007)\n", "N = int(input())\nprint((pow(27, N) - pow(7, N)) % (1000000000 + 7))\n", "test_mode = 0\n\ndef solver(n):\n\tn = int(n)\n\treturn (3 ** (3 * n) - 7 ** n) % (10 ** 9 + 7)\n\ndef compare_answer(xx, xy):\n\tif xx == xy:\n\t\tprint('Test passed\\n\\n')\n\telse:\n\t\tprint('Failed! Expected   >> {}\\n        Found      >> {}\\n\\n'.format(xy, xx))\n\ndef tprint(something):\n\tif test_mode:\n\t\tprint(something)\nif not test_mode:\n\tprint(solver(input()))\nelse:\n\tcompare_answer(solver(1), 20)\n\tcompare_answer(solver(2), 680)\n\tcompare_answer(solver(3), 19340)\n", "import sys\nf = sys.stdin\nn = int(f.readline().strip())\nrr = 10 ** 9 + 7\nni = 20\nnf = 27\nfor i in range(n - 1):\n\tni = 20 * nf + 7 * ni\n\tnf = 27 * nf\n\tif ni > rr:\n\t\tni = ni % rr\n\t\tnf = nf % rr\nprint(str(ni % rr))\n", "import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, copy, functools\ninf = 10 ** 20\neps = 1.0 / 10 ** 10\nmod = 10 ** 9 + 7\nmod2 = 998244353\ndd = [(-1, 0), (0, 1), (1, 0), (0, -1)]\nddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]\n\ndef LI():\n\treturn list(map(int, sys.stdin.readline().split()))\n\ndef LLI():\n\treturn [list(map(int, l.split())) for l in sys.stdin.readlines()]\n\ndef LI_():\n\treturn [int(x) - 1 for x in sys.stdin.readline().split()]\n\ndef LF():\n\treturn [float(x) for x in sys.stdin.readline().split()]\n\ndef LS():\n\treturn sys.stdin.readline().split()\n\ndef I():\n\treturn int(sys.stdin.readline())\n\ndef F():\n\treturn float(sys.stdin.readline())\n\ndef S():\n\treturn input()\n\ndef pf(s):\n\treturn print(s, flush=True)\n\ndef pe(s):\n\treturn print(str(s), file=sys.stderr)\n\ndef JA(a, sep):\n\treturn sep.join(map(str, a))\n\ndef JAA(a, s, t):\n\treturn s.join((t.join(map(str, b)) for b in a))\n\ndef IF(c, t, f):\n\treturn t if c else f\n\ndef YES(c):\n\treturn IF(c, 'YES', 'NO')\n\ndef Yes(c):\n\treturn IF(c, 'Yes', 'No')\n\ndef main():\n\tt = 1\n\trr = []\n\tfor _ in range(t):\n\t\tn = I()\n\t\trr.append((pow(27, n, mod) - pow(7, n, mod)) % mod)\n\treturn JA(rr, '\\n')\nprint(main())\n", "n = int(input())\nth = 1\nse = 1\ni = 1\nwhile i <= 3 * n:\n\tth = th * 3\n\tth = th % 1000000007\n\ti = i + 1\ni = 1\nwhile i <= n:\n\tse = se * 7\n\tse = se % 1000000007\n\ti = i + 1\nx = th - se\nif x < 0:\n\tx = x + 1000000007\nprint(x)\n", "n = int(input())\nM = int(1000000000.0 + 7)\nprint((pow(3, 3 * n, M) % M - pow(7, n, M) % M) % M)\n", "n = int(input())\np = 27 ** n % 1000000007\nc = 7 ** n % 1000000007\nprint((p - c) % 1000000007)\n", "n = int(input())\ns = 3 ** (3 * n) - 7 ** n\nprint(s % 1000000007)\n", "from math import floor\nMOD = 1000000007\nn = int(input())\nprint((27 ** n % MOD - 7 ** n % MOD) % MOD)\n", "n = int(input())\nm = 3 * n\nmod = 1000000007\ncont = 0\ncont = 3 ** m - 7 ** n\nprint(cont % mod)\n", "x = 10 ** 9 + 7\nn = int(input())\na = 27 ** (n % x)\nb = 7 ** (n % x)\nr = (a - b) % x\nprint(r)\n", "n = int(input(''))\nm = 1000000007\nprint((3 ** (3 * n) - 7 ** n) % m)\n", "n = int(input())\nmodulo = 1000000007\nres1 = pow(3, 3 * n, modulo)\nres2 = pow(7, n, modulo)\nres = (res1 - res2) % modulo\nprint(res)\n", "n = eval(input())\nprint((3 ** (3 * n) - 7 ** n) % 1000000007)\n", "n = int(input())\nmd = 10 ** 9 + 7\na = pow(27, n, md)\nb = pow(7, n, md)\nc = a - b\nif c < 0:\n\tc += md\nprint(c)\n", "n = int(input())\np = 3 ** (3 * n)\np -= 7 ** n\nprint(p % (10 ** 9 + 7))\n", "mod = 10 ** 9 + 7\n\ndef binpow(x, y):\n\tglobal mod\n\tres = 1\n\twhile y:\n\t\tif y & 1:\n\t\t\tres = res * x % mod\n\t\tx = x * x % mod\n\t\ty >>= 1\n\treturn res\nn = int(input())\nx = binpow(27, n) - binpow(7, n)\nif x < 0:\n\tx += mod\nx %= mod\nprint(x)\n", "n = int(input())\nM = 10 ** 9 + 7\nt1 = 0\nt2 = 0\nfor i in range(1, 4):\n\tfor j in range(1, 4):\n\t\tfor k in range(1, 4):\n\t\t\tif i + j + k == 6:\n\t\t\t\tt1 += 1\n\t\t\tt2 += 1\na1 = 1\na2 = 1\nfor i in range(n):\n\ta1 = a1 * t1 % M\n\ta2 = a2 * t2 % M\nans = ((a2 - a1) % M + M) % M\nprint(ans)\n", "n = int(input())\nk = 3 ** (3 * n) - 7 ** n\nprint(k % (10 ** 9 + 7))\n", "n = int(input())\nn27 = int(1)\nn7 = int(1)\nfor i in range(n):\n\tn27 = n27 * int(27)\n\tn7 = n7 * int(7)\n\tn27 = n27 % int(1000000000.0 + 7)\n\tn7 = n7 % int(1000000000.0 + 7)\nprint(int(n27 - n7) % int(1000000000.0 + 7))\n", "MOD = 1000000007\nn = int(input())\na = 27 ** n % MOD\nb = 7 ** n % MOD\nres = ((a - b) % MOD + MOD) % MOD\nprint(res)\n", "MOD = int(1000000007)\nn = int(input())\nall = int(1)\nfor i in range(3 * n):\n\tall = 3 * all % MOD\nbad = int(1)\nfor i in range(n):\n\tbad = 7 * bad % MOD\nans = all - bad\nif ans < 0:\n\tans += MOD\nprint(ans)\n", "n = int(input())\nbad = 7 ** n\nal = 3 ** (3 * n)\nprint((al - bad) % (10 ** 9 + 7))\n", "import itertools as it\nimport functools\nimport operator\nimport collections\nimport math\nimport sys\nBIG = 1000000007\n\ndef solve(n):\n\treturn (3 ** (3 * n) - (6 + 1) ** n) % BIG\n\ndef p(*args, **kwargs):\n\treturn print(*args, file=sys.stderr, **kwargs)\n\ndef main():\n\tn = int(input())\n\tresult = solve(n)\n\tprint(result)\nmain()\n", "import sys, os, io\n\ndef rs():\n\treturn sys.stdin.readline().rstrip()\n\ndef ri():\n\treturn int(sys.stdin.readline())\n\ndef ria():\n\treturn list(map(int, sys.stdin.readline().split()))\n\ndef ws(s):\n\tsys.stdout.write(s + '\\n')\n\ndef wi(n):\n\tsys.stdout.write(str(n) + '\\n')\n\ndef wia(a):\n\tsys.stdout.write(' '.join([str(x) for x in a]) + '\\n')\nimport math, datetime, functools, itertools, operator, bisect, fractions, statistics\nfrom collections import deque, defaultdict, OrderedDict, Counter\nfrom fractions import Fraction\nfrom decimal import Decimal\nfrom sys import stdout\nfrom heapq import heappush, heappop, heapify, _heapify_max, _heappop_max, nsmallest, nlargest\nsys.setrecursionlimit(111111)\nINF = 99999999999999999999999999999999\n\ndef main():\n\tmod = 1000000007\n\tstarttime = datetime.datetime.now()\n\tif os.path.exists('input.txt'):\n\t\tsys.stdin = open('input.txt', 'r')\n\t\tsys.stdout = open('output.txt', 'w')\n\ttc = 1\n\tfor _ in range(tc):\n\t\tn = ri()\n\t\tans1 = 1\n\t\tans2 = 1\n\t\tfor i in range(3 * n):\n\t\t\tans1 = ans1 * 3 % mod\n\t\tfor i in range(n):\n\t\t\tans2 = ans2 * 7 % mod\n\t\tprint((ans1 - ans2) % mod)\n\tendtime = datetime.datetime.now()\n\ttime = (endtime - starttime).total_seconds() * 1000\n\tif os.path.exists('input.txt'):\n\t\tprint('Time:', time, 'ms')\n\nclass FastReader(io.IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, fd, chunk_size=1024 * 8):\n\t\tself._fd = fd\n\t\tself._chunk_size = chunk_size\n\t\tself.buffer = io.BytesIO()\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self, size=-1):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\nclass FastWriter(io.IOBase):\n\n\tdef __init__(self, fd):\n\t\tself._fd = fd\n\t\tself.buffer = io.BytesIO()\n\t\tself.write = self.buffer.write\n\n\tdef flush(self):\n\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass FastStdin(io.IOBase):\n\n\tdef __init__(self, fd=0):\n\t\tself.buffer = FastReader(fd)\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n\nclass FastStdout(io.IOBase):\n\n\tdef __init__(self, fd=1):\n\t\tself.buffer = FastWriter(fd)\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.flush = self.buffer.flush\nsys.stdin = FastStdin()\nsys.stdout = FastStdout()\nmain()\n", "import time\nimport math\nn = int(input())\nstart = time.time()\nM = 1000000000 + 7\nans = 3 ** (3 * n) - 7 ** n\nprint(divmod(ans, M)[1])\nfinish = time.time()\n", "n = int(input())\nfirst = 3 ** (3 * n)\nsecond = 7 ** n\nmod = 1000000007\nprint((first - second) % mod)\n", "n = int(input())\nres = 1\nans = 1\nMOD = int(1000000000.0 + 7)\nfor i in range(n):\n\tres = res * 27 % MOD\n\tans = ans * 7 % MOD\nprint((res - ans + MOD) % MOD)\n", "import sys\nentry = int(sys.stdin.read())\nprint((3 ** (3 * entry) - 7 ** entry) % (10 ** 9 + 7))\n", "n = int(input())\nrem1 = 1\nfor i in range(3 * n):\n\trem1 *= 3\n\trem1 = rem1 % (7 + 10 ** 9)\nrem2 = 1\nfor i in range(n):\n\trem2 *= 7\n\trem2 = rem2 % (7 + 10 ** 9)\nans = (rem1 - rem2) % (7 + 10 ** 9)\nprint(ans)\n", "x = int(input())\ny = 3 ** (3 * x) - 7 ** x\nprint(y % 1000000007)\n", "import sys, re, math\nfrom collections import deque, defaultdict, Counter, OrderedDict\nfrom math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians\nfrom heapq import heappush, heappop, heapify, nlargest, nsmallest\n\ndef STR():\n\treturn list(input())\n\ndef INT():\n\treturn int(input())\n\ndef MAP():\n\treturn map(int, input().split())\n\ndef LIST():\n\treturn list(map(int, input().split()))\n\ndef list2d(a, b, c):\n\treturn [[c] * b for i in range(a)]\n\ndef sortListWithIndex(listOfTuples, idx):\n\treturn sorted(listOfTuples, key=lambda x: x[idx])\n\ndef sortDictWithVal(passedDic):\n\ttemp = sorted(passedDic.items(), key=lambda kv: (kv[1], kv[0]))[::-1]\n\ttoret = {}\n\tfor tup in temp:\n\t\ttoret[tup[0]] = tup[1]\n\treturn toret\n\ndef sortDictWithKey(passedDic):\n\treturn dict(OrderedDict(sorted(passedDic.items())))\nsys.setrecursionlimit(10 ** 9)\nINF = float('inf')\nmod = 10 ** 9 + 7\nn = INT()\nprint((3 ** (3 * n) - 7 ** n) % mod)\n", "n = int(input())\n\ndef solve(n):\n\tmod = 10 ** 9 + 7\n\tAs = [1, 2, 3]\n\tABCs = [a + b + c for a in As for b in As for c in As]\n\tk = len(ABCs)\n\tm = 20\n\treturn (pow(k, n, mod) - pow(7, n, mod)) % mod\nprint(solve(n))\n", "def main():\n\t(n, mod) = (int(input()), 1000000007)\n\tprint((pow(27, n, mod) - pow(7, n, mod)) % mod)\nmain()\n", "entrada = int(input())\nmod = 1000000007\nprint(((3 ** 3) ** entrada - 7 ** entrada) % mod)\n", "n = int(input())\nm = 1000000007\nprint((pow(27, n, m) - pow(7, n, m) + m) % m)\n", "n = int(input())\na = pow(3, 3 * n)\nb = pow(7, n)\nmod = int(pow(10, 9)) + 7\nprint((a - b + mod) % mod)\n", "def calc(n):\n\treturn (3 ** (3 * n) - 7 ** n) % (10 ** 9 + 7)\nn = int(input())\nprint(calc(n))\n", "mod = int(10 ** 9 + 7)\n\ndef power(a, n):\n\tres = 1\n\twhile n > 0:\n\t\tif n % 2 == 0:\n\t\t\ta = a * a % mod\n\t\t\tn //= 2\n\t\telse:\n\t\t\tn -= 1\n\t\t\tres = a * res % mod\n\treturn res\na = int(input())\nprint((power(3, a * 3) - power(7, a)) % mod)\n", "def exponenciacaoModular(a, b, c):\n\ta = a % c\n\tif a == 0:\n\t\treturn 0\n\tres = 1\n\twhile b > 0:\n\t\tif b % 2 != 0:\n\t\t\tres = res * a % c\n\t\t\tb -= 1\n\t\ta = a * a % c\n\t\tb = b // 2\n\treturn res\nc = 1000000007\nn = int(input())\nprint((exponenciacaoModular(3, 3 * n, c) - exponenciacaoModular(7, n, c)) % c)\n", "MOD = 1000000007\nn = int(input())\nans = 27 ** n - 7 ** n\nans %= MOD\nprint(ans)\n", "def pow(base, exp):\n\tres = 1\n\twhile exp:\n\t\tif exp & 1:\n\t\t\tres *= base\n\t\t\tres %= mod\n\t\tbase *= base\n\t\tbase %= mod\n\t\texp = exp >> 1\n\treturn res\nn = int(input())\nmod = 1000000007\nif n == 1:\n\tprint(20)\nelse:\n\tres1 = pow(27, n)\n\tres2 = pow(7, n)\n\tprint((res1 - res2 + mod) % mod)\n", "n = int(input())\nmod = 10 ** 9 + 7\n\ndef pow_mod(x, a):\n\ty = 1\n\tfor i in range(a):\n\t\ty *= x\n\t\tif y > mod:\n\t\t\ty %= mod\n\treturn y\nresult = pow_mod(27, n) - pow_mod(7, n)\nresult = (result + mod) % mod\nprint(result)\n", "n = int(input())\nx = pow(3, 3 * n) - pow(7, n)\nprint(x % (10 ** 9 + 7))\n", "import math\nimport sys\nn = int(input())\nmod = 10 ** 9 + 7\np3 = 1\np7 = 1\nfor i in range(3 * n):\n\tp3 = p3 * 3 % mod\nfor i in range(n):\n\tp7 = p7 * 7 % mod\nprint((p3 + mod - p7) % mod)\n", "MOD = 10 ** 9 + 7\nn = int(input())\nans = 20\nseven_degree = 1\nfor i in range(1, n):\n\tseven_degree *= 7\n\tseven_degree %= MOD\n\tans = (ans * 27 % MOD + seven_degree * 20) % MOD\nprint(ans)\n", "import os\nimport sys\nfrom io import BytesIO, IOBase\nfrom types import GeneratorType\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\timport os\n\t\tself.os = os\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = self.os.read(self._fd, max(self.os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tself.os.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\nimport time\nstart_time = time.time()\nimport collections as col\n\ndef getInts():\n\treturn [int(s) for s in input().split()]\n\ndef getInt():\n\treturn int(input())\n\ndef getStrs():\n\treturn [s for s in input().split()]\n\ndef getStr():\n\treturn input()\n\ndef listStr():\n\treturn list(input())\nseven_pows = [1]\ntwenty_seven_pows = [1]\nN = getInt()\nM = 10 ** 9 + 7\nfor j in range(N):\n\tseven_pows.append(seven_pows[-1] * 7 % M)\n\ttwenty_seven_pows.append(twenty_seven_pows[-1] * 27 % M)\n\ndef solve():\n\tans = 0\n\tfor i in range(N):\n\t\tans += seven_pows[i] * twenty_seven_pows[N - i - 1]\n\t\tans %= M\n\tans *= 20\n\tans %= M\n\treturn ans\nprint(solve())\n", "def variants(n):\n\treturn 3 ** (3 * n) - 7 ** n\nn = int(input())\nprint(variants(n) % (10 ** 9 + 7))\n", "import sys\ninput = sys.stdin.readline\nMOD = 10 ** 9 + 7\n\ndef pow_mod(mod):\n\n\tdef pow(base, exp):\n\t\tif exp <= 1:\n\t\t\treturn base ** exp % mod\n\t\telif exp % 2 == 0:\n\t\t\treturn (pow(base, exp // 2) % mod) ** 2 % mod\n\t\telse:\n\t\t\treturn pow(base, exp - 1) * base % mod\n\treturn pow\npow = pow_mod(mod=MOD)\nn = int(input())\nprint((pow(3, 3 * n) - pow(7, n)) % MOD)\n", "def solution():\n\tn = int(input())\n\tM = 10 ** 9 + 7\n\treturn rec(n, M)\n\ndef rec(n, M):\n\tif n == 1:\n\t\treturn 20\n\tif n % 2 == 1:\n\t\treturn (27 * rec(n - 1, M) + 20 * 7 ** (n - 1)) % M\n\telse:\n\t\tn = int(n / 2)\n\t\tx = rec(n, M)\n\t\treturn (x ** 2 + 2 * x * 7 ** n) % M\nprint(solution())\n", "entrada = int(input())\nmodulo = 1000000007\na = 1\nb = 1\nfor j in range(entrada):\n\tb = b * 7 % modulo\ntamanho = entrada * 3\nfor i in range(tamanho):\n\ta = a * 3 % modulo\nprint((a - b + modulo) % modulo)\n"]

difficulty: MEDIUM

source: codeforces

raw_problem:
B. Kolya and Tanya

time limit per test
1 second

memory limit per test
256 megabytes

input
standard input

output
standard output

Kolya loves putting gnomes at the circle table and giving them coins, and Tanya loves studying triplets of gnomes, sitting in the vertexes of an equilateral triangle.

More formally, there are 3n gnomes sitting in a circle. Each gnome can have from 1 to 3 coins. Let's number the places in the order they occur in the circle by numbers from 0 to 3n - 1, let the gnome sitting on the i-th place have ai coins. If there is an integer i (0 ≤ i < n) such that ai + ai + n + ai + 2n ≠ 6, then Tanya is satisfied.

Count the number of ways to choose ai so that Tanya is satisfied. As there can be many ways of distributing coins, print the remainder of this number modulo 109 + 7. Two ways, a and b, are considered distinct if there is index i (0 ≤ i < 3n), such that ai ≠ bi (that is, some gnome got different number of coins in these two ways).

Input

A single line contains number n (1 ≤ n ≤ 105) — the number of the gnomes divided by three.

Output

Print a single number — the remainder of the number of variants of distributing coins that satisfy Tanya modulo 109 + 7.

Examples

Input

1

Output

20

Input

2

Output

680

Note

20 ways for n = 1 (gnome with index 0 sits on the top of the triangle, gnome 1 on the right vertex, gnome 2 on the left vertex):

question:
Kolya loves putting gnomes at the circle table and giving them coins, and Tanya loves studying triplets of gnomes, sitting in the vertexes of an equilateral triangle.
More formally, there are 3n gnomes sitting in a circle. Each gnome can have from 1 to 3 coins. Let's number the places in the order they occur in the circle by numbers from 0 to 3n - 1, let the gnome sitting on the i-th place have a_{i} coins. If there is an integer i (0 ≤ i < n) such that a_{i} + a_{i + n} + a_{i + 2n} ≠ 6, then Tanya is satisfied.
Count the number of ways to choose a_{i} so that Tanya is satisfied. As there can be many ways of distributing coins, print the remainder of this number modulo 10^{9} + 7. Two ways, a and b, are considered distinct if there is index i (0 ≤ i < 3n), such that a_{i} ≠ b_{i} (that is, some gnome got different number of coins in these two ways).

Input
A single line contains number n (1 ≤ n ≤ 10^{5}) — the number of the gnomes divided by three.

Output
Print a single number — the remainder of the number of variants of distributing coins that satisfy Tanya modulo 10^{9} + 7.

Examples
Input
1

Output
20

Input
2

Output
680

Note
20 ways for n = 1 (gnome with index 0 sits on the top of the triangle, gnome 1 on the right vertex, gnome 2 on the left vertex): ![image](1.png)

data_split: test


H. Squid Game

problem_index: H

time_limit: 2 seconds

memory_limit: 256 megabytes

note:
Explanation for the first sample:
![image](images/cf_1610_H/1.png) In the first operation, Mashtali can choose vertex $$$1$$$ and eliminate players with colors red and blue. In the second operation, he can choose vertex $$$6$$$ and eliminate the player with orange color.
In the second sample, Mashtali can't eliminate the first player.

source: codeforces

raw_problem:
H. Squid Game

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

After watching the new over-rated series Squid Game, Mashtali and Soroush decided to hold their own Squid Games! Soroush agreed to be the host and will provide money for the winner's prize, and Mashtali became the Front Man!

$$$m$$$ players registered to play in the games to win the great prize, but when Mashtali found out how huge the winner's prize is going to be, he decided to kill eliminate all the players so he could take the money for himself!

Here is how evil Mashtali is going to eliminate players:

There is an unrooted tree with $$$n$$$ vertices. Every player has $$$2$$$ special vertices $$$x_i$$$ and $$$y_i$$$.

In one operation, Mashtali can choose any vertex $$$v$$$ of the tree. Then, for each remaining player $$$i$$$ he finds a vertex $$$w$$$ on the simple path from $$$x_i$$$ to $$$y_i$$$, which is the closest to $$$v$$$. If $$$w\ne x_i$$$ and $$$w\ne y_i$$$, player $$$i$$$ will be eliminated.

Now Mashtali wondered: "What is the minimum number of operations I should perform so that I can remove every player from the game and take the money for myself?"

Since he was only thinking about the money, he couldn't solve the problem by himself and asked for your help!

Input

The first line contains $$$2$$$ integer $$$n$$$ and $$$m$$$ $$$(1 \le n, m \le 3 \cdot 10^5)$$$ — the number of vertices of the tree and the number of players.

The second line contains $$$n-1$$$ integers $$$par_2, par_3, \ldots, par_n$$$ $$$(1 \le par_i < i)$$$ — denoting an edge between node $$$i$$$ and $$$par_i$$$.

The $$$i$$$-th of the following $$$m$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ $$$(1 \le x_i, y_i \le n, x_i \ne y_i)$$$ — the special vertices of the $$$i$$$-th player.

Output

Print the minimum number of operations Mashtali has to perform.

If there is no way for Mashtali to eliminate all the players, print $$$-1$$$.

Examples

Input

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

Output

2

Input

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

Output

-1

Note

Explanation for the first sample:
  In the first operation, Mashtali can choose vertex $$$1$$$ and eliminate players with colors red and blue. In the second operation, he can choose vertex $$$6$$$ and eliminate the player with orange color.
In the second sample, Mashtali can't eliminate the first player.

question:
After watching the new over-rated series Squid Game, Mashtali and Soroush decided to hold their own Squid Games! Soroush agreed to be the host and will provide money for the winner's prize, and Mashtali became the Front Man!
$$$m$$$ players registered to play in the games to win the great prize, but when Mashtali found out how huge the winner's prize is going to be, he decided to kill eliminate all the players so he could take the money for himself!
Here is how evil Mashtali is going to eliminate players:
There is an unrooted tree with $$$n$$$ vertices. Every player has $$$2$$$ special vertices $$$x_i$$$ and $$$y_i$$$.
In one operation, Mashtali can choose any vertex $$$v$$$ of the tree. Then, for each remaining player $$$i$$$ he finds a vertex $$$w$$$ on the simple path from $$$x_i$$$ to $$$y_i$$$, which is the closest to $$$v$$$. If $$$w\ne x_i$$$ and $$$w\ne y_i$$$, player $$$i$$$ will be eliminated.
Now Mashtali wondered: "What is the minimum number of operations I should perform so that I can remove every player from the game and take the money for myself?"
Since he was only thinking about the money, he couldn't solve the problem by himself and asked for your help!

Input
The first line contains $$$2$$$ integer $$$n$$$ and $$$m$$$ $$$(1 \le n, m \le 3 \cdot 10^5)$$$ — the number of vertices of the tree and the number of players.
The second line contains $$$n-1$$$ integers $$$par_2, par_3, \ldots, par_n$$$ $$$(1 \le par_i < i)$$$ — denoting an edge between node $$$i$$$ and $$$par_i$$$.
The $$$i$$$-th of the following $$$m$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ $$$(1 \le x_i, y_i \le n, x_i \ne y_i)$$$ — the special vertices of the $$$i$$$-th player.

Output
Print the minimum number of operations Mashtali has to perform.
If there is no way for Mashtali to eliminate all the players, print $$$-1$$$.

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

Output
2

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

Output
-1

Note
Explanation for the first sample:
 ![image](1.png) In the first operation, Mashtali can choose vertex $$$1$$$ and eliminate players with colors red and blue. In the second operation, he can choose vertex $$$6$$$ and eliminate the player with orange color. In the second sample, Mashtali can't eliminate the first player.

data_split: test


F1. Smooth Sailing (Easy Version)

problem_raw:
F1. Smooth Sailing (Easy Version)

time limit per test
5 seconds

memory limit per test
1024 megabytes

input
standard input

output
standard output

The only difference between the two versions of this problem is the constraint on $$$q$$$. You can make hacks only if both versions of the problem are solved.

Thomas is sailing around an island surrounded by the ocean. The ocean and island can be represented by a grid with $$$n$$$ rows and $$$m$$$ columns. The rows are numbered from $$$1$$$ to $$$n$$$ from top to bottom, and the columns are numbered from $$$1$$$ to $$$m$$$ from left to right. The position of a cell at row $$$r$$$ and column $$$c$$$ can be represented as $$$(r, c)$$$. Below is an example of a valid grid.
  Example of a valid grid
There are three types of cells: island, ocean and underwater volcano. Cells representing the island are marked with a '#', cells representing the ocean are marked with a '.', and cells representing an underwater volcano are marked with a 'v'. It is guaranteed that there is at least one island cell and at least one underwater volcano cell. It is also guaranteed that the set of all island cells forms a single connected component$$$^{\dagger}$$$ and the set of all ocean cells and underwater volcano cells forms a single connected component. Additionally, it is guaranteed that there are no island cells at the edge of the grid (that is, at row $$$1$$$, at row $$$n$$$, at column $$$1$$$, and at column $$$m$$$).

Define a round trip starting from cell $$$(x, y)$$$ as a path Thomas takes which satisfies the following conditions:

 The path starts and ends at $$$(x, y)$$$.

 If Thomas is at cell $$$(i, j)$$$, he can go to cells $$$(i+1, j)$$$, $$$(i-1, j)$$$, $$$(i, j-1)$$$, and $$$(i, j+1)$$$ as long as the destination cell is an ocean cell or an underwater volcano cell and is still inside the grid. Note that it is allowed for Thomas to visit the same cell multiple times in the same round trip.

 The path must go around the island and fully encircle it. Some path $$$p$$$ fully encircles the island if it is impossible to go from an island cell to a cell on the grid border by only traveling to adjacent on a side or diagonal cells without visiting a cell on path $$$p$$$. In the image below, the path starting from $$$(2, 2)$$$, going to $$$(1, 3)$$$, and going back to $$$(2, 2)$$$ the other way does not fully encircle the island and is not considered a round trip.

  Example of a path that does not fully encircle the island
The safety of a round trip is the minimum Manhattan distance$$$^{\ddagger}$$$ from a cell on the round trip to an underwater volcano (note that the presence of island cells does not impact this distance).

You have $$$q$$$ queries. A query can be represented as $$$(x, y)$$$ and for every query, you want to find the maximum safety of a round trip starting from $$$(x, y)$$$. It is guaranteed that $$$(x, y)$$$ is an ocean cell or an underwater volcano cell.

$$$^{\dagger}$$$A set of cells forms a single connected component if from any cell of this set it is possible to reach any other cell of this set by moving only through the cells of this set, each time going to a cell with a common side.

$$$^{\ddagger}$$$Manhattan distance between cells $$$(r_1, c_1)$$$ and $$$(r_2, c_2)$$$ is equal to $$$|r_1 - r_2| + |c_1 - c_2|$$$.

Input

The first line contains three integers $$$n$$$, $$$m$$$, and $$$q$$$ ($$$3 \leq n, m \leq 10^5$$$, $$$9 \leq n \cdot m \leq 3 \cdot 10^5$$$, $$$1 \leq q \leq 5$$$) — the number of rows and columns of the grid and the number of queries.

Each of the following $$$n$$$ lines contains $$$m$$$ characters describing the cells of the grid. The character '#' denotes an island cell, '.' denotes an ocean cell, and 'v' denotes an underwater volcano cell.

It is guaranteed that there is at least one island cell and at least one underwater volcano cell. It is guaranteed that the set of all island cells forms a single connected component and the set of all ocean cells and underwater volcano cells forms a single connected component. Also, it is guaranteed that there are no island cells at the edge of the grid (that is, at the row $$$1$$$, at the row $$$n$$$, at the column $$$1$$$, and at the column $$$m$$$).

The following $$$q$$$ lines describe the queries. Each of these lines contains two integers $$$x$$$ and $$$y$$$ ($$$1 \leq x \leq n$$$, $$$1 \leq y \leq m$$$) denoting a round trip starting from $$$(x, y)$$$.

It is guaranteed that $$$(x, y)$$$ is an ocean cell or an underwater volcano cell.

Output

For each query, output a single integer — the maximum safety of a round trip starting from the specified position.

Examples

Input

9 9 3
.........
.........
....###..
...v#....
..###....
...##...v
...##....
.........
v........
1 1
9 1
5 7

Output

3
0
3

Input

3 3 5
..v
.#.
...
1 2
1 3
2 3
2 1
3 2

Output

0
0
0
0
0

Input

14 13 5
.............
.............
.............
...vvvvvvv...
...v.....v...
...v.###.v...
...v.#.#.v...
...v..v..v...
...v..v..v...
....v...v....
.....vvv.....
.............
.............
.............
1 1
7 7
5 6
4 10
13 6

Output

3
0
1
0
2

Input

10 11 4
...........
..#######..
..#..#..#..
..#.....#..
..#..v..#..
..#.###.#..
..#.#.#.#..
..#...#.#..
..#####.#..
...........
7 6
3 7
6 8
1 1

Output

1
2
3
4

Note

For the first example, the image below shows an optimal round trip starting from $$$(1, 1)$$$. The round trip has a safety of $$$3$$$ as the minimum Manhattan distance from a cell on the round trip to an underwater volcano is $$$3$$$.
  Example of an optimal round trip
For the fourth example, remember that it is allowed for Thomas to visit the same cell multiple times in the same round trip. For example, doing so is necessary for the round trip starting from $$$(7, 6)$$$.

time_limit: 5 seconds

memory_limit: 1024 megabytes

input:
9 9 3
.........
.........
....###..
...v#....
..###....
...##...v
...##....
.........
v........
1 1
9 1
5 7

output:
3
0
3

input:
3 3 5
..v
.#.
...
1 2
1 3
2 3
2 1
3 2

output:
0
0
0
0
0

input:
14 13 5
.............
.............
.............
...vvvvvvv...
...v.....v...
...v.###.v...
...v.#.#.v...
...v..v..v...
...v..v..v...
....v...v....
.....vvv.....
.............
.............
.............
1 1
7 7
5 6
4 10
13 6

output:
3
0
1
0
2

input:
10 11 4
...........
..#######..
..#..#..#..
..#.....#..
..#..v..#..
..#.###.#..
..#.#.#.#..
..#...#.#..
..#####.#..
...........
7 6
3 7
6 8
1 1

output:
1
2
3
4

question:
The only difference between the two versions of this problem is the constraint on $$$q$$$. You can make hacks only if both versions of the problem are solved.
Thomas is sailing around an island surrounded by the ocean. The ocean and island can be represented by a grid with $$$n$$$ rows and $$$m$$$ columns. The rows are numbered from $$$1$$$ to $$$n$$$ from top to bottom, and the columns are numbered from $$$1$$$ to $$$m$$$ from left to right. The position of a cell at row $$$r$$$ and column $$$c$$$ can be represented as $$$(r, c)$$$. Below is an example of a valid grid.
 ![image](1.png) Example of a valid grid There are three types of cells: island, ocean and underwater volcano. Cells representing the island are marked with a '#', cells representing the ocean are marked with a '.', and cells representing an underwater volcano are marked with a 'v'. It is guaranteed that there is at least one island cell and at least one underwater volcano cell. It is also guaranteed that the set of all island cells forms a single connected component$$$^{\dagger}$$$ and the set of all ocean cells and underwater volcano cells forms a single connected component. Additionally, it is guaranteed that there are no island cells at the edge of the grid (that is, at row $$$1$$$, at row $$$n$$$, at column $$$1$$$, and at column $$$m$$$).
Define a round trip starting from cell $$$(x, y)$$$ as a path Thomas takes which satisfies the following conditions:
 -  The path starts and ends at $$$(x, y)$$$. -  If Thomas is at cell $$$(i, j)$$$, he can go to cells $$$(i+1, j)$$$, $$$(i-1, j)$$$, $$$(i, j-1)$$$, and $$$(i, j+1)$$$ as long as the destination cell is an ocean cell or an underwater volcano cell and is still inside the grid. Note that it is allowed for Thomas to visit the same cell multiple times in the same round trip. -  The path must go around the island and fully encircle it. Some path $$$p$$$ fully encircles the island if it is impossible to go from an island cell to a cell on the grid border by only traveling to adjacent on a side or diagonal cells without visiting a cell on path $$$p$$$. In the image below, the path starting from $$$(2, 2)$$$, going to $$$(1, 3)$$$, and going back to $$$(2, 2)$$$ the other way does not fully encircle the island and is not considered a round trip.  ![image](2.png) Example of a path that does not fully encircle the island The safety of a round trip is the minimum Manhattan distance$$$^{\ddagger}$$$ from a cell on the round trip to an underwater volcano (note that the presence of island cells does not impact this distance).
You have $$$q$$$ queries. A query can be represented as $$$(x, y)$$$ and for every query, you want to find the maximum safety of a round trip starting from $$$(x, y)$$$. It is guaranteed that $$$(x, y)$$$ is an ocean cell or an underwater volcano cell.
$$$^{\dagger}$$$A set of cells forms a single connected component if from any cell of this set it is possible to reach any other cell of this set by moving only through the cells of this set, each time going to a cell with a common side.
$$$^{\ddagger}$$$Manhattan distance between cells $$$(r_1, c_1)$$$ and $$$(r_2, c_2)$$$ is equal to $$$|r_1 - r_2| + |c_1 - c_2|$$$.

Input
The first line contains three integers $$$n$$$, $$$m$$$, and $$$q$$$ ($$$3 \leq n, m \leq 10^5$$$, $$$9 \leq n \cdot m \leq 3 \cdot 10^5$$$, $$$1 \leq q \leq 5$$$) — the number of rows and columns of the grid and the number of queries.
Each of the following $$$n$$$ lines contains $$$m$$$ characters describing the cells of the grid. The character '#' denotes an island cell, '.' denotes an ocean cell, and 'v' denotes an underwater volcano cell.
It is guaranteed that there is at least one island cell and at least one underwater volcano cell. It is guaranteed that the set of all island cells forms a single connected component and the set of all ocean cells and underwater volcano cells forms a single connected component. Also, it is guaranteed that there are no island cells at the edge of the grid (that is, at the row $$$1$$$, at the row $$$n$$$, at the column $$$1$$$, and at the column $$$m$$$).
The following $$$q$$$ lines describe the queries. Each of these lines contains two integers $$$x$$$ and $$$y$$$ ($$$1 \leq x \leq n$$$, $$$1 \leq y \leq m$$$) denoting a round trip starting from $$$(x, y)$$$.
It is guaranteed that $$$(x, y)$$$ is an ocean cell or an underwater volcano cell.

Output
For each query, output a single integer — the maximum safety of a round trip starting from the specified position.

Examples
Input

9 9 3
.........
.........
....###..
...v#....
..###....
...##...v
...##....
.........
v........
1 1
9 1
5 7

Output

3
0
3

Input

3 3 5
..v
.#.
...
1 2
1 3
2 3
2 1
3 2

Output

0
0
0
0
0

Input

14 13 5
.............
.............
.............
...vvvvvvv...
...v.....v...
...v.###.v...
...v.#.#.v...
...v..v..v...
...v..v..v...
....v...v....
.....vvv.....
.............
.............
.............
1 1
7 7
5 6
4 10
13 6

Output

3
0
1
0
2

Input

10 11 4
...........
..#######..
..#..#..#..
..#.....#..
..#..v..#..
..#.###.#..
..#.#.#.#..
..#...#.#..
..#####.#..
...........
7 6
3 7
6 8
1 1

Output

1
2
3
4

Note
For the first example, the image below shows an optimal round trip starting from $$$(1, 1)$$$. The round trip has a safety of $$$3$$$ as the minimum Manhattan distance from a cell on the round trip to an underwater volcano is $$$3$$$.
 ![image](3.png) Example of an optimal round trip For the fourth example, remember that it is allowed for Thomas to visit the same cell multiple times in the same round trip. For example, doing so is necessary for the round trip starting from $$$(7, 6)$$$.

source: codeforces

image_tags: Map Map Map

data_split: test