20240208

# k = 0

# memo = []

#

#

# def f(a, b, m, n, puddle):

# global k

# k = k % 1000000007

# if a == m and b == n:

# k += 1

# return

# if a == m:

# if puddle[a][b + 1] == 0:

# f(a, b + 1, m, n, puddle)

# elif b == n:

# if puddle[a + 1][b] == 0:

# f(a + 1, b, m, n, puddle)

# else:

# if puddle[a][b + 1] == 0:

# f(a, b + 1, m, n, puddle)

# if puddle[a + 1][b] == 0:

# f(a + 1, b, m, n, puddle)

# k = 0

# memo = []

#

#

# def g(a, b, m, n):

# global memo, k

# k = k % 1000000007

# u = m - a

# v = n - b

# if memo[u][v] != 0:

# return memo[u][v]

# l = 1

# for i in range(u + 1, u + v + 1, 1):

# l *= i

# for i in range(2, v + 1, 1):

# l //= i

# memo[u][v] = l

# return l

#

#

# def solution(m, n, puddles):

# global k, memo

# z = len(puddles)

# for i in range(m + 1):

# v = [0] * (n + 1)

# memo.append(v)

# k += g(1, 1, m, n)

# for i1 in range(z):

# k -= g(1, 1, puddles[i1][0], puddles[i1][1]) * g(puddles[i1][0], puddles[i1][1], m, n)

#

# if z >= 2:

# for i1 in range(z):

# for i2 in range(z):

# if i2 == i1:

# continue

# if puddles[i1][0] <= puddles[i2][0] and puddles[i1][1] <= puddles[i2][1]:

# k += g(1, 1, puddles[i1][0], puddles[i1][1]) g(puddles[i1][0], puddles[i1][1], puddles[i2][0], puddles[i2][1]) g(puddles[i2][0], puddles[i2][1], m, n)

# if z >= 3:

# for i1 in range(z):

# for i2 in range(z):

# if i2 == i1:

# continue

# if puddles[i1][0] > puddles[i2][0]:

# continue

# if puddles[i1][1] > puddles[i2][1]:

# continue

# for i3 in range(z):

# if i3 == i1:

# continue

# if i3 == i2:

# continue

# if puddles[i1][0] <= puddles[i2][0] <= puddles[i3][0] and puddles[i1][1] <= puddles[i2][1] <= puddles[i3][1]:

# k -= g(1, 1, puddles[i1][0], puddles[i1][1]) g(puddles[i1][0], puddles[i1][1], puddles[i2][0], puddles[i2][1]) g(puddles[i2][0], puddles[i2][1], puddles[i3][0], puddles[i3][1]) * g(puddles[i3][0], puddles[i3][1], m, n)

#

# if z >= 4:

# for i1 in range(z):

# for i2 in range(z):

# if i2 == i1:

# continue

# if puddles[i1][0] > puddles[i2][0]:

# continue

# if puddles[i1][1] > puddles[i2][1]:

# continue

# for i3 in range(z):

# if i3 == i1:

# continue

# if i3 == i2:

# continue

# if puddles[i1][0] > puddles[i3][0]:

# continue

# if puddles[i2][0] > puddles[i3][0]:

# continue

# if puddles[i1][1] > puddles[i3][1]:

# continue

# if puddles[i2][1] > puddles[i3][1]:

# continue

# for i4 in range(z):

# if i4 == i1:

# continue

# if i4 == i2:

# continue

# if i4 == i3:

# continue

# if puddles[i1][0] <= puddles[i2][0] <= puddles[i3][0] <= puddles[i4][0] and puddles[i1][1] <= puddles[i2][1] <= puddles[i3][1] <= puddles[i4][1]:

# k += g(1, 1, puddles[i1][0], puddles[i1][1]) g(puddles[i1][0], puddles[i1][1], puddles[i2][0], puddles[i2][1]) g(puddles[i2][0], puddles[i2][1], puddles[i3][0], puddles[i3][1]) g(puddles[i3][0], puddles[i3][1], puddles[i4][0], puddles[i4][1]) g(puddles[i4][0], puddles[i4][1], m, n)

#

# if z >= 5:

# for i1 in range(z):

# for i2 in range(z):

# if i2 == i1:

# continue

# if puddles[i1][0] > puddles[i2][0]:

# continue

# if puddles[i1][1] > puddles[i2][1]:

# continue

# for i3 in range(z):

# if i3 == i1:

# continue

# if i3 == i2:

# continue

# if puddles[i1][0] > puddles[i3][0]:

# continue

# if puddles[i2][0] > puddles[i3][0]:

# continue

# if puddles[i1][1] > puddles[i3][1]:

# continue

# if puddles[i2][1] > puddles[i3][1]:

# continue

# for i4 in range(z):

# if i4 == i1:

# continue

# if i4 == i2:

# continue

# if i4 == i3:

# continue

# if puddles[i1][0] > puddles[i4][0]:

# continue

# if puddles[i2][0] > puddles[i4][0]:

# continue

# if puddles[i3][0] > puddles[i4][0]:

# continue

# if puddles[i1][1] > puddles[i4][1]:

# continue

# if puddles[i2][1] > puddles[i4][1]:

# continue

# if puddles[i3][1] > puddles[i4][1]:

# continue

# for i5 in range(z):

# if i5 == i1:

# continue

# if i5 == i2:

# continue

# if i5 == i3:

# continue

# if i5 == i4:

# continue

# if puddles[i1][0] <= puddles[i2][0] <= puddles[i3][0] <= puddles[i4][0] <= puddles[i5][0] and puddles[i1][1] <= puddles[i2][1] <= puddles[i3][1] <= puddles[i4][1] <= puddles[i5][1]:

# k -= g(1, 1, puddles[i1][0], puddles[i1][1]) g(puddles[i1][0], puddles[i1][1], puddles[i2][0], puddles[i2][1]) g(puddles[i2][0], puddles[i2][1], puddles[i3][0], puddles[i3][1]) g(puddles[i3][0], puddles[i3][1], puddles[i4][0], puddles[i4][1]) g(puddles[i4][0], puddles[i4][1], puddles[i5][0], puddles[i5][1]) * g(puddles[i5][0], puddles[i5][1], m, n)

#

# if z >= 6:

# for i1 in range(z):

# for i2 in range(z):

# if i2 == i1:

# continue

# if puddles[i1][0] > puddles[i2][0]:

# continue

# if puddles[i1][1] > puddles[i2][1]:

# continue

# for i3 in range(z):

# if i3 == i1:

# continue

# if i3 == i2:

# continue

# if puddles[i1][0] > puddles[i3][0]:

# continue

# if puddles[i2][0] > puddles[i3][0]:

# continue

# if puddles[i1][1] > puddles[i3][1]:

# continue

# if puddles[i2][1] > puddles[i3][1]:

# continue

# for i4 in range(z):

# if i4 == i1:

# continue

# if i4 == i2:

# continue

# if i4 == i3:

# continue

# if puddles[i1][0] > puddles[i4][0]:

# continue

# if puddles[i2][0] > puddles[i4][0]:

# continue

# if puddles[i3][0] > puddles[i4][0]:

# continue

# if puddles[i1][1] > puddles[i4][1]:

# continue

# if puddles[i2][1] > puddles[i4][1]:

# continue

# if puddles[i3][1] > puddles[i4][1]:

# continue

# for i5 in range(z):

# if i5 == i1:

# continue

# if i5 == i2:

# continue

# if i5 == i3:

# continue

# if i5 == i4:

# continue

# if puddles[i1][0] > puddles[i5][0]:

# continue

# if puddles[i2][0] > puddles[i5][0]:

# continue

# if puddles[i3][0] > puddles[i5][0]:

# continue

# if puddles[i4][0] > puddles[i5][0]:

# continue

# if puddles[i1][1] > puddles[i5][1]:

# continue

# if puddles[i2][1] > puddles[i5][1]:

# continue

# if puddles[i3][1] > puddles[i5][1]:

# continue

# if puddles[i4][1] > puddles[i5][1]:

# continue

# for i6 in range(z):

# if i6 == i1:

# continue

# if i6 == i2:

# continue

# if i6 == i3:

# continue

# if i6 == i4:

# continue

# if i6 == i5:

# continue

# if puddles[i1][0] <= puddles[i2][0] <= puddles[i3][0] <= puddles[i4][0] <= puddles[i5][0] <= puddles[i6][0] and puddles[i1][1] <= puddles[i2][1] <= puddles[i3][1] <= puddles[i4][1] <= puddles[i5][1] <= puddles[i6][1]:

# k += g(1, 1, puddles[i1][0], puddles[i1][1]) g(puddles[i1][0], puddles[i1][1], puddles[i2][0], puddles[i2][1]) g(puddles[i2][0], puddles[i2][1], puddles[i3][0], puddles[i3][1]) g(puddles[i3][0], puddles[i3][1], puddles[i4][0], puddles[i4][1]) g(puddles[i4][0], puddles[i4][1], puddles[i5][0], puddles[i5][1]) g(puddles[i5][0], puddles[i5][1], puddles[i6][0], puddles[i6][1]) g(puddles[i6][0], puddles[i6][1], m, n)

#

# if z >= 7:

# for i1 in range(z):

# for i2 in range(z):

# if i2 == i1:

# continue

# if puddles[i1][0] > puddles[i2][0]:

# continue

# if puddles[i1][1] > puddles[i2][1]:

# continue

# for i3 in range(z):

# if i3 == i1:

# continue

# if i3 == i2:

# continue

# if puddles[i1][0] > puddles[i3][0]:

# continue

# if puddles[i2][0] > puddles[i3][0]:

# continue

# if puddles[i1][1] > puddles[i3][1]:

# continue

# if puddles[i2][1] > puddles[i3][1]:

# continue

# for i4 in range(z):

# if i4 == i1:

# continue

# if i4 == i2:

# continue

# if i4 == i3:

# continue

# if puddles[i1][0] > puddles[i4][0]:

# continue

# if puddles[i2][0] > puddles[i4][0]:

# continue

# if puddles[i3][0] > puddles[i4][0]:

# continue

# if puddles[i1][1] > puddles[i4][1]:

# continue

# if puddles[i2][1] > puddles[i4][1]:

# continue

# if puddles[i3][1] > puddles[i4][1]:

# continue

# for i5 in range(z):

# if i5 == i1:

# continue

# if i5 == i2:

# continue

# if i5 == i3:

# continue

# if i5 == i4:

# continue

# if puddles[i1][0] > puddles[i5][0]:

# continue

# if puddles[i2][0] > puddles[i5][0]:

# continue

# if puddles[i3][0] > puddles[i5][0]:

# continue

# if puddles[i4][0] > puddles[i5][0]:

# continue

# if puddles[i1][1] > puddles[i5][1]:

# continue

# if puddles[i2][1] > puddles[i5][1]:

# continue

# if puddles[i3][1] > puddles[i5][1]:

# continue

# if puddles[i4][1] > puddles[i5][1]:

# continue

# for i6 in range(z):

# if i6 == i1:

# continue

# if i6 == i2:

# continue

# if i6 == i3:

# continue

# if i6 == i4:

# continue

# if i6 == i5:

# continue

# for i7 in range(z):

# if i7 == i1:

# continue

# if i7 == i2:

# continue

# if i7 == i3:

# continue

# if i7 == i4:

# continue

# if i7 == i5:

# continue

# if i7 == i6:

# continue

# if puddles[i1][0] <= puddles[i2][0] <= puddles[i3][0] <= puddles[i4][0] <= puddles[i5][0] <= puddles[i6][0] <= puddles[i7][0] and puddles[i1][1] <= puddles[i2][1] <= puddles[i3][1] <= puddles[i4][1] <= puddles[i5][1] <= puddles[i6][1] <= puddles[i7][1]:

# k -= g(1, 1, puddles[i1][0], puddles[i1][1]) g(puddles[i1][0], puddles[i1][1], puddles[i2][0], puddles[i2][1]) g(puddles[i2][0], puddles[i2][1], puddles[i3][0], puddles[i3][1]) g(puddles[i3][0], puddles[i3][1], puddles[i4][0], puddles[i4][1]) g(puddles[i4][0], puddles[i4][1], puddles[i5][0], puddles[i5][1]) g(puddles[i5][0], puddles[i5][1], puddles[i6][0], puddles[i6][1]) g(puddles[i6][0], puddles[i6][1], puddles[i7][0], puddles[i7][1]) * g(puddles[i7][0], puddles[i7][1], m, n)

#

# if z >= 8:

# for i1 in range(z):

# for i2 in range(z):

# if i2 == i1:

# continue

# if puddles[i1][0] > puddles[i2][0]:

# continue

# if puddles[i1][1] > puddles[i2][1]:

# continue

# for i3 in range(z):

# if i3 == i1:

# continue

# if i3 == i2:

# continue

# if puddles[i1][0] > puddles[i3][0]:

# continue

# if puddles[i2][0] > puddles[i3][0]:

# continue

# if puddles[i1][1] > puddles[i3][1]:

# continue

# if puddles[i2][1] > puddles[i3][1]:

# continue

# for i4 in range(z):

# if i4 == i1:

# continue

# if i4 == i2:

# continue

# if i4 == i3:

# continue

# if puddles[i1][0] > puddles[i4][0]:

# continue

# if puddles[i2][0] > puddles[i4][0]:

# continue

# if puddles[i3][0] > puddles[i4][0]:

# continue

# if puddles[i1][1] > puddles[i4][1]:

# continue

# if puddles[i2][1] > puddles[i4][1]:

# continue

# if puddles[i3][1] > puddles[i4][1]:

# continue

# for i5 in range(z):

# if i5 == i1:

# continue

# if i5 == i2:

# continue

# if i5 == i3:

# continue

# if i5 == i4:

# continue

# if puddles[i1][0] > puddles[i5][0]:

# continue

# if puddles[i2][0] > puddles[i5][0]:

# continue

# if puddles[i3][0] > puddles[i5][0]:

# continue

# if puddles[i4][0] > puddles[i5][0]:

# continue

# if puddles[i1][1] > puddles[i5][1]:

# continue

# if puddles[i2][1] > puddles[i5][1]:

# continue

# if puddles[i3][1] > puddles[i5][1]:

# continue

# if puddles[i4][1] > puddles[i5][1]:

# continue

# for i6 in range(z):

# if i6 == i1:

# continue

# if i6 == i2:

# continue

# if i6 == i3:

# continue

# if i6 == i4:

# continue

# if i6 == i5:

# continue

# for i7 in range(z):

# if i7 == i1:

# continue

# if i7 == i2:

# continue

# if i7 == i3:

# continue

# if i7 == i4:

# continue

# if i7 == i5:

# continue

# if i7 == i6:

# continue

# for i8 in range(z):

# if i8 == i1:

# continue

# if i8 == i2:

# continue

# if i8 == i3:

# continue

# if i8 == i4:

# continue

# if i8 == i5:

# continue

# if i8 == i6:

# continue

# if i8 == i7:

# continue

# if puddles[i1][0] <= puddles[i2][0] <= puddles[i3][0] <= puddles[i4][0] <= puddles[i5][0] <= puddles[i6][0] <= puddles[i7][0] <= puddles[i8][0] and puddles[i1][1] <= puddles[i2][1] <= puddles[i3][1] <= puddles[i4][1] <= puddles[i5][1] <= puddles[i6][1] <= puddles[i7][1] <= puddles[i8][1]:

# k += g(1, 1, puddles[i1][0], puddles[i1][1]) g(puddles[i1][0], puddles[i1][1], puddles[i2][0], puddles[i2][1]) g(puddles[i2][0], puddles[i2][1], puddles[i3][0], puddles[i3][1]) g(puddles[i3][0], puddles[i3][1], puddles[i4][0], puddles[i4][1]) g(puddles[i4][0], puddles[i4][1], puddles[i5][0], puddles[i5][1]) g(puddles[i5][0], puddles[i5][1], puddles[i6][0], puddles[i6][1]) g(puddles[i6][0], puddles[i6][1], puddles[i7][0], puddles[i7][1]) g(puddles[i7][0], puddles[i7][1], puddles[i8][0], puddles[i8][1]) g(puddles[i8][0], puddles[i8][1], m, n)

#

# if z >= 9:

# for i1 in range(z):

# for i2 in range(z):

# if i2 == i1:

# continue

# if puddles[i1][0] > puddles[i2][0]:

# continue

# if puddles[i1][1] > puddles[i2][1]:

# continue

# for i3 in range(z):

# if i3 == i1:

# continue

# if i3 == i2:

# continue

# if puddles[i1][0] > puddles[i3][0]:

# continue

# if puddles[i2][0] > puddles[i3][0]:

# continue

# if puddles[i1][1] > puddles[i3][1]:

# continue

# if puddles[i2][1] > puddles[i3][1]:

# continue

# for i4 in range(z):

# if i4 == i1:

# continue

# if i4 == i2:

# continue

# if i4 == i3:

# continue

# if puddles[i1][0] > puddles[i4][0]:

# continue

# if puddles[i2][0] > puddles[i4][0]:

# continue

# if puddles[i3][0] > puddles[i4][0]:

# continue

# if puddles[i1][1] > puddles[i4][1]:

# continue

# if puddles[i2][1] > puddles[i4][1]:

# continue

# if puddles[i3][1] > puddles[i4][1]:

# continue

# for i5 in range(z):

# if i5 == i1:

# continue

# if i5 == i2:

# continue

# if i5 == i3:

# continue

# if i5 == i4:

# continue

# if puddles[i1][0] > puddles[i5][0]:

# continue

# if puddles[i2][0] > puddles[i5][0]:

# continue

# if puddles[i3][0] > puddles[i5][0]:

# continue

# if puddles[i4][0] > puddles[i5][0]:

# continue

# if puddles[i1][1] > puddles[i5][1]:

# continue

# if puddles[i2][1] > puddles[i5][1]:

# continue

# if puddles[i3][1] > puddles[i5][1]:

# continue

# if puddles[i4][1] > puddles[i5][1]:

# continue

# for i6 in range(z):

# if i6 == i1:

# continue

# if i6 == i2:

# continue

# if i6 == i3:

# continue

# if i6 == i4:

# continue

# if i6 == i5:

# continue

# for i7 in range(z):

# if i7 == i1:

# continue

# if i7 == i2:

# continue

# if i7 == i3:

# continue

# if i7 == i4:

# continue

# if i7 == i5:

# continue

# if i7 == i6:

# continue

# for i8 in range(z):

# if i8 == i1:

# continue

# if i8 == i2:

# continue

# if i8 == i3:

# continue

# if i8 == i4:

# continue

# if i8 == i5:

# continue

# if i8 == i6:

# continue

# if i8 == i7:

# continue

# for i9 in range(z):

# if i9 == i1:

# continue

# if i9 == i2:

# continue

# if i9 == i3:

# continue

# if i9 == i4:

# continue

# if i9 == i5:

# continue

# if i9 == i6:

# continue

# if i9 == i7:

# continue

# if i9 == i8:

# continue

# if puddles[i1][0] <= puddles[i2][0] <= puddles[i3][0] <= puddles[i4][0] <= puddles[i5][0] <= puddles[i6][0] <= puddles[i7][0] <= puddles[i8][0] <= puddles[i9][0] and puddles[i1][1] <= puddles[i2][1] <= puddles[i3][1] <= puddles[i4][1] <= puddles[i5][1] <= puddles[i6][1] <= puddles[i7][1] <= puddles[i8][1] <= puddles[i9][1]:

# k -= g(1, 1, puddles[i1][0], puddles[i1][1]) g(puddles[i1][0], puddles[i1][1], puddles[i2][0], puddles[i2][1]) g(puddles[i2][0], puddles[i2][1], puddles[i3][0], puddles[i3][1]) g(puddles[i3][0], puddles[i3][1], puddles[i4][0], puddles[i4][1]) g(puddles[i4][0], puddles[i4][1], puddles[i5][0], puddles[i5][1]) g(puddles[i5][0], puddles[i5][1], puddles[i6][0], puddles[i6][1]) g(puddles[i6][0], puddles[i6][1], puddles[i7][0], puddles[i7][1]) g(puddles[i7][0], puddles[i7][1], puddles[i8][0], puddles[i8][1]) g(puddles[i8][0], puddles[i8][1], puddles[i9][0], puddles[i9][1]) * g(puddles[i9][0], puddles[i9][1], m, n)

#

# if z >= 10:

# for i1 in range(z):

# for i2 in range(z):

# if i2 == i1:

# continue

# if puddles[i1][0] > puddles[i2][0]:

# continue

# if puddles[i1][1] > puddles[i2][1]:

# continue

# for i3 in range(z):

# if i3 == i1:

# continue

# if i3 == i2:

# continue

# if puddles[i1][0] > puddles[i3][0]:

# continue

# if puddles[i2][0] > puddles[i3][0]:

# continue

# if puddles[i1][1] > puddles[i3][1]:

# continue

# if puddles[i2][1] > puddles[i3][1]:

# continue

# for i4 in range(z):

# if i4 == i1:

# continue

# if i4 == i2:

# continue

# if i4 == i3:

# continue

# if puddles[i1][0] > puddles[i4][0]:

# continue

# if puddles[i2][0] > puddles[i4][0]:

# continue

# if puddles[i3][0] > puddles[i4][0]:

# continue

# if puddles[i1][1] > puddles[i4][1]:

# continue

# if puddles[i2][1] > puddles[i4][1]:

# continue

# if puddles[i3][1] > puddles[i4][1]:

# continue

# for i5 in range(z):

# if i5 == i1:

# continue

# if i5 == i2:

# continue

# if i5 == i3:

# continue

# if i5 == i4:

# continue

# if puddles[i1][0] > puddles[i5][0]:

# continue

# if puddles[i2][0] > puddles[i5][0]:

# continue

# if puddles[i3][0] > puddles[i5][0]:

# continue

# if puddles[i4][0] > puddles[i5][0]:

# continue

# if puddles[i1][1] > puddles[i5][1]:

# continue

# if puddles[i2][1] > puddles[i5][1]:

# continue

# if puddles[i3][1] > puddles[i5][1]:

# continue

# if puddles[i4][1] > puddles[i5][1]:

# continue

# for i6 in range(z):

# if i6 == i1:

# continue

# if i6 == i2:

# continue

# if i6 == i3:

# continue

# if i6 == i4:

# continue

# if i6 == i5:

# continue

# for i7 in range(z):

# if i7 == i1:

# continue

# if i7 == i2:

# continue

# if i7 == i3:

# continue

# if i7 == i4:

# continue

# if i7 == i5:

# continue

# if i7 == i6:

# continue

# for i8 in range(z):

# if i8 == i1:

# continue

# if i8 == i2:

# continue

# if i8 == i3:

# continue

# if i8 == i4:

# continue

# if i8 == i5:

# continue

# if i8 == i6:

# continue

# if i8 == i7:

# continue

# for i9 in range(z):

# if i9 == i1:

# continue

# if i9 == i2:

# continue

# if i9 == i3:

# continue

# if i9 == i4:

# continue

# if i9 == i5:

# continue

# if i9 == i6:

# continue

# if i9 == i7:

# continue

# if i9 == i8:

# continue

# for i10 in range(z):

# if i10 == i1:

# continue

# if i10 == i2:

# continue

# if i10 == i3:

# continue

# if i10 == i4:

# continue

# if i10 == i5:

# continue

# if i10 == i6:

# continue

# if i10 == i7:

# continue

# if i10 == i8:

# continue

# if i10 == i9:

# continue

# if puddles[i1][0] <= puddles[i2][0] <= puddles[i3][0] <= puddles[i4][0] <= puddles[i5][0] <= puddles[i6][0] <= puddles[i7][0] <= puddles[i8][0] <= puddles[i9][0] <= puddles[i10][0] and puddles[i1][1] <= puddles[i2][1] <= puddles[i3][1] <= puddles[i4][1] <= puddles[i5][1] <= puddles[i6][1] <= puddles[i7][1] <= puddles[i8][1] <= puddles[i9][1] <= puddles[i10][1]:

# k += g(1, 1, puddles[i1][0], puddles[i1][1]) g(puddles[i1][0], puddles[i1][1], puddles[i2][0], puddles[i2][1]) g(puddles[i2][0], puddles[i2][1], puddles[i3][0], puddles[i3][1]) g(puddles[i3][0], puddles[i3][1], puddles[i4][0], puddles[i4][1]) g(puddles[i4][0], puddles[i4][1], puddles[i5][0], puddles[i5][1]) g(puddles[i5][0], puddles[i5][1], puddles[i6][0], puddles[i6][1]) g(puddles[i6][0], puddles[i6][1], puddles[i7][0], puddles[i7][1]) g(puddles[i7][0], puddles[i7][1], puddles[i8][0], puddles[i8][1]) g(puddles[i8][0], puddles[i8][1], puddles[i9][0], puddles[i9][1]) g(puddles[i9][0], puddles[i9][1], puddles[i10][0], puddles[i10][1]) g(puddles[i10][0], puddles[i10][1], m, n)

#

# k = k % 1000000007

# answer = k

# return answer

#

#

# m, n = map(int, input().split())

# p = []

# for i in range(2):

# v = list(map(int, input().split()))

# p.append(v)

# print(solution(m, n, p))

def solution(N, number):

answer = -1

d = []

for i in range(8):

if i == 0:

v = [N]

else:

v = [1, 0]

for j in range(len(d[i - 1])):

v.append(d[i-1][j] * 2)

v.append(d[i-1][j] * 11)

v.append(d[i-1][j] * d[i-1][j])

d.append(v)

for i in range(8):

for j in range(len(d[i])):

if d[i][j] == number:

answer = i + 1

break

return answer