Problem:


Score : 1800 points

Problem Statement

We have a round pizza. Snuke wants to eat one third of it, or something as close as possible to that.

He decides to cut this pizza as follows.

First, he divides the pizza into N pieces by making N cuts with a knife. The knife can make a cut along the segment connecting the center of the pizza and some point on the circumference of the pizza. However, he is very poor at handling knives, so the cuts are made at uniformly random angles, independent from each other.

Then, he chooses one or more consecutive pieces so that the total is as close as possible to one third of the pizza, and eat them. (Let the total be x of the pizza. He chooses consecutive pieces so that |x - 1/3| is minimized.)

Find the expected value of |x - 1/3|. It can be shown that this value is rational, and we ask you to print it modulo 10^9 + 7, as described in Notes.

Notes

When you print a rational number, first write it as a fraction \frac{y}{x}, where x, y are integers and x is not divisible by 10^9 + 7
(under the constraints of the problem, such representation is always possible).
Then, you need to print the only integer z between 0 and 10^9 + 6, inclusive, that satisfies xz \equiv y \pmod{10^9 + 7}.

Constraints

2 \leq N \leq 10^6

Input

Input is given from Standard Input in the following format:

N

Output

Print the expected value of |x - 1/3| modulo 10^9 + 7, as described in Notes.

Sample Input 1

2

Sample Output 1

138888890

The expected value is \frac{5}{36}.

Sample Input 2

3

Sample Output 2

179012347

The expected value is \frac{11}{162}.

Sample Input 3

10

Sample Output 3

954859137

Sample Input 4

1000000

Sample Output 4

44679646



Sample input:
2


Sample output:
138888890

Submission status: Wrong Answer

Solution code:
import numpy as np

N, MOD = int(input()), 10 ** 9 + 7
Inv3 = 333333336

A=[-1]*(N+1)
B=[-1]*(N+1)
G=[-1]*(N+1)

A[0]=1
B[0]=0
G[0]=0

for i in range(N):
    A[i+1]=(B[i]+G[i]) % MOD
    B[i+1]=(A[i]+G[i]) % MOD
    G[i+1]=(A[i]+B[i]) % MOD


inv_int  =[1]*(N+1)
fact     =[1]*(N+1)
inv_fact =[1]*(N+1)
for i in range(1,N+1):

    a=i
    b=MOD
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)

    inv_int[i]=lastx % MOD

    fact[i]=(fact[i-1]*i) % MOD
    inv_fact[i]=inv_fact[i-1]*inv_int[i] % MOD


    
ans=0
for k in range(1,N+1):
    comb= ( inv_fact[k] * inv_fact[N-k] ) % MOD
    ans=( ans + B[k] * comb * inv_int[k] ) % MOD

a=np.power(3,N)
b=MOD
(x, lastx) = (0, 1)
(y, lasty) = (1, 0)
while b != 0:
    q = a // b
    (a, b) = (b, a % b)
    (x, lastx) = (lastx - q * x, x)
    (y, lasty) = (lasty - q * y, y)


ans= ans * fact[N-1] * lastx % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def cmb(n, r):
    global mod
    if ( r<0 or r>n ):
        return 1
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

def f(n,r):
  return cmb(n+r-1,r)

mod = 10**9+7 #出力の制限
N = int(input())
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N*2 + 3 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )

DP=[[1,0,0]]
for i in range(N):
  DP.append([(DP[i][1]+DP[i][2])%mod,(DP[i][0]+DP[i][2])%mod,(DP[i][1]+DP[i][0])%mod])
DP
P=0
pow2=2
X=pow(pow(3,N,mod)*N,mod-2,mod)
for i in range(N):
  P=(P+(DP[i+1][1]*f(N-i,i+1)*pow(i+1,mod-2,mod)))%mod
  pow2=(pow2*2)%mod
print((P*X)%mod)

Submission status: Time Limit Exceeded

Solution code:
MOD = 10**9 + 7
MAX_N = 10**6

pow2 = [1] * (MAX_N+1)
fact = [1] * (MAX_N+1)
fact_inv = [1] * (MAX_N+1)


def mod_inv(n: int, mod: int)->int:
    b, u, v = mod, 1, 0
    while b > 0:
        t = n // b

        n -= t * b
        u -= t * v

        n, b = b, n
        u, v = v, u

    return (u+mod) % mod


def init(N: int):
    global pow2, fact, fact_inv
    for n in range(N):
        pow2[n+1] = (2 * pow2[n]) % MOD
        fact[n+1] = ((n+1) * fact[n]) % MOD

    fact_inv[N] = mod_inv(fact[N], MOD)
    for n in range(N, 0, -1):
        fact_inv[n-1] = (n * fact_inv[n]) % MOD


def comb(n: int, r: int)->int:
    global fact, fact_inv
    return (fact[n] * fact_inv[n-r] * fact_inv[r]) % MOD


def bin_pow(a: int, n: int, mod: int)->int:
    # if n == 0:
    #     return 1
    # if n & 1:
    #     t = bin_pow(a, n-1, mod)
    #     return (a * t) % mod

    # t = bin_pow(a, n >> 1, mod)
    # return (t * t) % mod

    res = 1
    while n > 0:
        if n & 1:
            res *= a
            res %= mod
        a *= a
        a %= MOD
        n >>= 1
    return res


def one_third(N: int)->int:
    ans = 0
    for i in range(1, N+1):
        w = pow2[i]
        if i & 1:
            w = (w+1) % MOD
        else:
            w = (w-1) % MOD
        # ans = (ans + comb(N, i) * w * mod_inv(i, MOD)) % MOD
        ans += comb(N, i) * w * bin_pow(i, MOD-2, MOD)
        ans %= MOD

    ans *= mod_inv(bin_pow(3, N+1, MOD), MOD)
    ans %= MOD
    ans *= mod_inv(N, MOD)
    ans %= MOD

    return ans


if __name__ == "__main__":
    N = int(input())

    init(N)
    # print('init fin')

    ans = one_third(N)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
def mod_inv(n: int, mod: int)->int:
    b, u, v = mod, 1, 0
    while b > 0:
        t = n // b

        n -= t * b
        u -= t * v

        n, b = b, n
        u, v = v, u

    return (u+mod) % mod


def bin_pow(a: int, n: int, mod: int)->int:
    if n == 0:
        return 1
    if n & 1:
        t = bin_pow(a, n-1, mod)
        return (a * t) % mod

    t = bin_pow(a, n >> 1, mod)
    return (t * t) % mod


def one_third(N: int)->int:
    MOD = 10**9 + 7

    pow2 = [1] * (N+1)
    fact = [1] * (N+1)
    fact_inv = [1] * (N+1)
    for n in range(N):
        pow2[n+1] = (2 * pow2[n]) % MOD
        fact[n+1] = ((n+1) * fact[n]) % MOD
        fact_inv[n+1] = mod_inv(fact[n+1], MOD)

    def comb(n: int, r: int)->int:
        return (fact[n] * fact_inv[n-r] * fact_inv[r]) % MOD

    ans = 0
    for i in range(1, N+1):
        w = pow2[i]
        if i & 1:
            w = (w+1) % MOD
        else:
            w = (w-1) % MOD
        ans = (ans + comb(N, i) * w * mod_inv(i, MOD)) % MOD

    ans *= mod_inv(bin_pow(3, N+1, MOD), MOD)
    ans %= MOD
    ans *= mod_inv(N, MOD)
    ans %= MOD

    return ans


if __name__ == "__main__":
    N = int(input())

    ans = one_third(N)
    print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, MOD = int(input()), 10 ** 9 + 7
Inv3 = 333333336

A=[-1]*(N+1)
B=[-1]*(N+1)
G=[-1]*(N+1)

A[0]=1
B[0]=0
G[0]=0

for i in range(N):
    A[i+1]=(B[i]+G[i]) % MOD
    B[i+1]=(A[i]+G[i]) % MOD
    G[i+1]=(A[i]+B[i]) % MOD


inv_int  =[1]*(N+1)
fact     =[1]*(N+1)
inv_fact =[1]*(N+1)
for i in range(1,N+1):

    a=i
    b=MOD
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)

    inv_int[i]=lastx % MOD

    fact[i]=(fact[i-1]*i) % MOD
    inv_fact[i]=inv_fact[i-1]*inv_int[i] % MOD


    
ans=0
for k in range(1,N+1):
    comb= ( inv_fact[k] * inv_fact[N-k] ) % MOD
    ans=( ans + B[k] * comb * inv_int[k] ) % MOD

a=3**N
b=MOD
(x, lastx) = (0, 1)
(y, lasty) = (1, 0)
while b != 0:
    q = a // b
    (a, b) = (b, a % b)
    (x, lastx) = (lastx - q * x, x)
    (y, lasty) = (lasty - q * y, y)


ans= ans * fact[N-1] * lastx % MOD
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
 
# ax ≡ 1 (mod m)なるxを返す
def modinv(a, m):
    (inv, q, gcd_val) = egcd(a, m)
    return inv % m



N, MOD = int(input()), 10 ** 9 + 7

A=[-1 for i in range(N+1)]
B=[-1 for i in range(N+1)]
G=[-1 for i in range(N+1)]

A[0]=1
B[0]=0
G[0]=0

for i in range(N):
    A[i+1]=(B[i]+G[i]) % MOD
    B[i+1]=(A[i]+G[i]) % MOD
    G[i+1]=(A[i]+B[i]) % MOD



fact=[1]*(N+1)
for i in range(1,N+1):
    fact[i]=(fact[i-1]*i) % MOD

    
ans=0
for k in range(1,N+1):
    comb= (fact[N]) % MOD
    ans=( ans + B[k] * comb * modinv( (fact[k] * fact[N-k] * 3**N*N*k) % MOD , MOD) ) % MOD
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
 
# ax ≡ 1 (mod m)なるxを返す
def modinv(a, m):
    (inv, q, gcd_val) = egcd(a, m)
    return inv % m



N, MOD = int(input()), 10 ** 9 + 7

A=[-1 for i in range(N+1)]
B=[-1 for i in range(N+1)]
G=[-1 for i in range(N+1)]

A[0]=1
B[0]=0
G[0]=0

for i in range(N):
    A[i+1]=(B[i]+G[i]) % MOD
    B[i+1]=(A[i]+G[i]) % MOD
    G[i+1]=(A[i]+B[i]) % MOD



fact=[1]*(N+1)
fact_inv=[1]*(N+1)
for i in range(1,N+1):
    fact[i]=(fact[i-1]*i) % MOD
    fact_inv[i]=modinv(fact[i],MOD)

    
ans=0
for k in range(1,N+1):
    comb= ( fact[N] * fact_inv[k] * fact_inv[N-k] ) % MOD
    ans=( ans + B[k] * comb * modinv(3**N*N*k,MOD) ) % MOD
 
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import math

def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)
 
# ax ≡ 1 (mod m)なるxを返す
def modinv(a, m):
    (inv, q, gcd_val) = egcd(a, m)
    return inv % m



N, MOD = int(input()), 10 ** 9 + 7

A=[-1 for i in range(N+1)]
B=[-1 for i in range(N+1)]
G=[-1 for i in range(N+1)]

A[0]=1
B[0]=0
G[0]=0

for i in range(N):
    A[i+1]=B[i]+G[i]
    B[i+1]=A[i]+G[i]
    G[i+1]=A[i]+B[i]


ans=0
for k in range(1,N+1):
    comb = ( math.factorial(N) // (math.factorial(k)*math.factorial(N - k)) ) %MOD
    ans=( ans + B[k] * comb * modinv(3**N*N*k,MOD) ) % MOD
 
print(ans)

Submission status: Runtime Error

Solution code:
N, MOD = int(input()), 10 ** 9 + 7

A=[[-1 for i in range(N+1)] for j in range(N+1)]
B=[[-1 for i in range(N+1)] for j in range(N+1)]
G=[[-1 for i in range(N+1)] for j in range(N+1)]

A[0][0]=1
B[0][0]=0
G[0][0]=0


def countA(n,k):
    if A[n][k]!=-1:
        return A[n][k]
    elif n==0:
        A[n][k]=0
        return A[n][k]
    else:
        A[n][k]=countA(n-1,k)+countB(n-1,k-1)+countG(n-1,k-1)
        return A[n][k]


def countB(n,k):
    if B[n][k]!=-1:
        return B[n][k]
    elif n==0:
        B[n][k]=0
        return B[n][k]
    else:
        B[n][k]=countA(n-1,k-1)+countB(n-1,k)+countG(n-1,k-1)
        return B[n][k]


def countG(n,k):
    if G[n][k]!=-1:
        return G[n][k]
    elif n==0:
        G[n][k]=0
        return G[n][k]
    else:
        G[n][k]=countA(n-1,k-1)+countB(n-1,k-1)+countG(n-1,k)
        return G[n][k]
        
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)

# ax ≡ 1 (mod m)なるxを返す
def modinv(a, m):
    (inv, q, gcd_val) = egcd(a, m)
    return inv % m



ans=0
for k in range(1,N+1):
    ans=( ans + countB(N,k) * modinv(3**N*N*k,MOD) ) % MOD

print(ans)

Submission status: Runtime Error

Solution code:
N, MOD = int(input()), 10 ** 9 + 7

A=[[-1 for i in range(N+1)] for j in range(N+1)]
B=[[-1 for i in range(N+1)] for j in range(N+1)]
G=[[-1 for i in range(N+1)] for j in range(N+1)]

A[0][0]=1
B[0][0]=0
G[0][0]=0


def countA(n,k):
    if A[n][k]!=-1:
        return A[n][k]
    elif n==0:
        A[n][k]=0
        return A[n][k]
    else:
        A[n][k]=countA(n-1,k)+countB(n-1,k-1)+countG(n-1,k-1)
        return A[n][k]


def countB(n,k):
    if B[n][k]!=-1:
        return B[n][k]
    elif n==0:
        B[n][k]=0
        return B[n][k]
    else:
        B[n][k]=countA(n-1,k-1)+countB(n-1,k)+countG(n-1,k-1)
        return B[n][k]


def countG(n,k):
    if G[n][k]!=-1:
        return G[n][k]
    elif n==0:
        G[n][k]=0
        return G[n][k]
    else:
        G[n][k]=countA(n-1,k-1)+countB(n-1,k-1)+countG(n-1,k)
        return G[n][k]
        
def egcd(a, b):
    (x, lastx) = (0, 1)
    (y, lasty) = (1, 0)
    while b != 0:
        q = a // b
        (a, b) = (b, a % b)
        (x, lastx) = (lastx - q * x, x)
        (y, lasty) = (lasty - q * y, y)
    return (lastx, lasty, a)

# ax ≡ 1 (mod m)なるxを返す
def modinv(a, m):
    (inv, q, gcd_val) = egcd(a, m)
    return inv % m



ans=0
for k in range(1,N+1):
    print(countB(N,k),3**N*N*k)
    ans=( ans + countB(N,k) * modinv(3**N*N*k,MOD) ) % MOD

print(ans)

Submission status: Runtime Error

Solution code:
勇気のsub...

Submission status: Runtime Error

Solution code:
n = int(input())
list = []
a = []
for i in range(n):
  list.append(int(input))

for i in range(1, n):
  for j in range(1, i):
    if list[i] == j:
      a.insert(j, j)

if a == list:
  for i in range(n):
    print(list[i])
else:
  print(-1)