Problem:


Score : 1000 points

Problem Statement

Takahashi and Snuke came up with a game that uses a number sequence, as follows:

Prepare a sequence of length M consisting of integers between 0 and 2^N-1 (inclusive): a = a_1, a_2, \ldots, a_M.

Snuke first does the operation below as many times as he likes:

Choose a positive integer d, and for each i (1 \leq i \leq M), in binary, set the d-th least significant bit of a_i to 0. (Here the least significant bit is considered the 1-st least significant bit.)

After Snuke finishes doing operations, Takahashi tries to sort a in ascending order by doing the operation below some number of times. Here a is said to be in ascending order when a_i \leq a_{i + 1} for all i (1 \leq i \leq M - 1).

Choose two adjacent elements of a: a_i and a_{i + 1}. If, in binary, these numbers differ in exactly one bit, swap a_i and a_{i + 1}.

There are 2^{NM} different sequences of length M consisting of integers between 0 and 2^N-1 that can be used in the game.

How many among them have the following property: if used in the game, there is always a way for Takahashi to sort the sequence in ascending order regardless of Snuke's operations? Find the count modulo (10^9 + 7).

Constraints

All values in input are integers.

1 \leq N \leq 5000

2 \leq M \leq 5000

Input

Input is given from Standard Input in the following format:

N M

Output

Print the number, modulo (10^9 + 7), of sequences with the property: if used in the game, there is always a way for Takahashi to sort the sequence in ascending order regardless of Snuke's operations.

Sample Input 1

2 5

Sample Output 1

352

Consider the case a = 1, 3, 1, 3, 1 for example.

When the least significant bit of each element of a is set to 0, a = 0, 2, 0, 2, 0;

When the second least significant bit of each element of a is set to 0, a = 1, 1, 1, 1, 1;

When the least two significant bits of each element of a are set to 0, a = 0, 0, 0, 0, 0.

In all of the cases above and the case when Snuke does no operation to change a, we can sort the sequence by repeatedly swapping adjacent elements that differ in exactly one bit.
Thus, this sequence has the property: if used in the game, there is always a way for Takahashi to sort the sequence in ascending order regardless of Snuke's operations.

Sample Input 2

2020 530

Sample Output 2

823277409



Sample input:
2 5


Sample output:
352

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')
fact = [i for i in range(10**5+1)]
fact[0] = 1
for i in range(10**5):
  fact[i+1]*=fact[i]
  fact[i+1]%=mod
invfact=[None]*(10**5+1)
invfact[-1]=pow(fact[-1],mod-2,mod)
for i in range(10**5):
  invfact[-i-2]=(invfact[-i-1]*(10**5-i))%mod

def cmb(n,k):
  return fact[n]*invfact[k]*invfact[n-k]%mod
#solve
def solve():
    n, m = LI()
    dp = [[0, 0] for i in range(n + 1)]
    dp[0][0] = 1
    dp[1][0] = n
    dp[1][1] = n
    for i in range(1,n):
        dp[i + 1][0] = cmb(n,i)
        dp[i + 1][1] = cmb(n,i)*i%mod
    ans = pow(2, m, mod)
    tmp = 0
    for d1, d2 in dp:
        tmp += d1 + d2
        tmp %= mod
    print(ans * tmp % mod)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')
fact = [i for i in range(10**5+1)]
fact[0] = 1
for i in range(10**5):
  fact[i+1]*=fact[i]
  fact[i+1]%=mod
invfact=[None]*(10**5+1)
invfact[-1]=pow(fact[-1],mod-2,mod)
for i in range(10**5):
  invfact[-i-2]=(invfact[-i-1]*(10**5-i))%mod

def cmb(n,k):
  return fact[n]*invfact[k]*invfact[n-k]%mod
#solve
def solve():
    n, m = LI()
    dp = [[0, 0] for i in range(n + 1)]
    dp[0][0] = 1
    dp[1][0] = n
    dp[1][1] = n
    for i in range(1,n):
        dp[i + 1][0] = cmb(n,i)
        dp[i + 1][1] = cmb(n,i)*(i+1)%mod
    ans = pow(2, m, mod)
    tmp = 0
    for d1, d2 in dp:
        tmp += d1 + d2
        tmp %= mod
    print(ans * tmp % mod)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
class comb():
  F = [1, 1]
  Fi = [1, 1]
  I = [0, 1]
  def __init__(self, num, mod):
    self.MOD = mod
    for i in range(2, num + 1):
      self.F.append((self.F[-1] * i) % mod)
      self.I.append(mod - self.I[mod % i] * (mod // i) % mod)
      self.Fi.append(self.Fi[-1] * self.I[i] % mod)
  def com(self, n, k):
    if n < k: return 0
    if n < 0 or k < 0: return 0
    return self.F[n] * (self.Fi[k] * self.Fi[n - k] % self.MOD) % self.MOD


M, N = list(map(int, input().split()))
MOD = 10 ** 9 + 7
DP = [[[0] * 2 for i in range(M + 1)] for _ in range(N)]

com = comb(M + 1, MOD)

L = [0] * (M + 1)
for i in range(M + 1):
  L[i] = com.com(M, i)

for i in range(M + 1):
  DP[0][i][0] = 1

for i in range(1, N):
  for j in range(M + 1):
    if j != 0:
      DP[i][j][0] += (DP[i - 1][j - 1][0] + DP[i - 1][j - 1][1]) * L[j - 1] % MOD
    DP[i][j][0] += DP[i - 1][j][0] * L[j] % MOD
    DP[i][j][0] %= MOD

    if j != M:
      DP[i][j][1] += (DP[i - 1][j + 1][0]) * L[j + 1] % MOD
    DP[i][j][1] += DP[i - 1][j][1] * L[j] % MOD

ans = 0
for i in range(M + 1):
  ans = (ans + DP[-1][i][0] + DP[-1][i][1]) % MOD

print(ans)

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    n, m = LI()
    dp = [[0, 0] for i in range(n + 1)]
    dp[0][0] = 1
    for i in range(n):
        dp[i + 1][0] = dp[i][0] * (n - i) % mod
        dp[i + 1][1] = (dp[i][1] * (n - i) * i + dp[i][0] * (n - i)) % mod
    ans = pow(2, m, mod)
    tmp = 0
    for d1, d2 in dp:
        tmp += d1 + d2
        tmp %= mod
    print(ans * tmp % mod)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
from collections import defaultdict,deque
from heapq import heappush, heappop
from bisect import bisect_left, bisect_right
import sys, random, itertools, math
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
sqrt = math.sqrt
def LI(): return list(map(int, input().split()))
def LF(): return list(map(float, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def II(): return int(input())
def IF(): return float(input())
def S(): return input().rstrip()
def LS(): return S().split()
def IR(n): return [II() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def FR(n): return [IF() for _ in range(n)]
def LFR(n): return [LI() for _ in range(n)]
def LIR_(n): return [LI_() for _ in range(n)]
def SR(n): return [S() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
mod = 1000000007
inf = float('INF')

#solve
def solve():
    n, m = LI()
    dp = [[0, 0] for i in range(n + 1)]
    dp[0][0] = 1
    for i in range(n):
        dp[i + 1][0] = dp[i][0] * (n - i) % mod
        dp[i + 1][1] = (dp[i][1] * (n - i) + dp[i][0] * (n - i)) % mod
    ans = pow(2, m, mod)
    tmp = 0
    for d1, d2 in dp:
        tmp += d1 + d2
        tmp %= mod
    print(ans * tmp % mod)
    return


#main
if __name__ == '__main__':
    solve()

Submission status: Wrong Answer

Solution code:
input()
print(1)

Submission status: Accepted

Solution code:
import sys
import numpy as np

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

MOD = 10**9 + 7

N, M = map(int, read().split())

def make_power(a, L, MOD=MOD):
    B = L.bit_length()
    x = np.empty(1 << B, np.int64)
    x[0] = 1
    for n in range(B):
        x[1 << n:1 << (n + 1)] = x[:1 << n] * a % MOD
        a *= a
        a %= MOD
    x = x[:L]
    x.flags.writeable = False
    return x

pow2 = make_power(2, M + 10)
ipow2 = make_power((1 + MOD) // 2, M + 10)

def update(dp):
    B = dp.copy()
    C = dp * np.arange(M + 1) % MOD * ipow2[:M + 1] % MOD
    dp[1:] = np.cumsum(C[:-1]) % MOD
    dp[1:] *= pow2[:M]
    dp %= MOD
    dp += np.arange(1, M + 2) * B
    dp %= MOD

dp = pow2[:M + 1].copy()
for _ in range(N - 1):
    update(dp)

print(dp[-1])

Submission status: Runtime Error

Solution code:
import itertools
N = int(input())
A = [int(_) for _ in input().split()]
if A[0] != 0:
    if N == 0 and A[0] == 1:
        print(1)
    else:
        print(-1)
    exit()
ans = 1
n = 1
if A[0] > 1:
    print(-1)
    exit()
cumr = list(itertools.accumulate(A[::-1]))[::-1]
for i in range(1, N + 1):
    n = min(2 * (n - A[i - 1]), cumr[i])
    ans += n
    if n < 0:
        print(-1)
        exit()
print(ans)