# Задача №3002. Пилообразные последовательности - 210101010101010101010
#
# Назовем последовательность пилообразной, если каждый ее элемент либо строго больше, либо строго меньше своих соседей. По данными числам n и k определите число пилообразных последовательностей длины n, составленных из чисел 1..k.
# Входные данные
#
# Программа получает на вход два натуральных числа n и k,  1≤n≤1000, 1≤k≤1000.
# Выходные данные
#
# Необходимо вывести остаток от деления количества искомых последовательностей на 109+7.


# n = 3, k = 3, answer = 10
# n = 30, k = 3, answer = 4356618

def solve(n, k):
    print(n, k)
    if n == 0 or k == 0 or (n > 1 and k == 1):
        return 0
    elif n == 1 and k > 1:
        return k


# k,n = 0
# Always 0
print("n = 0, k = 2, answer ", solve(0, 2)) # 0
print("n = 6, k = 0, answer ", solve(6, 0)) # 0

# n > 1, k = 1
# always 0
print("n = 2, k = 1, answer ", solve(2, 1)) # 0

# n = 1, k > 1
# always k
print("n = 1, k = 2, answer ", solve(2, 1)) # 1 2

# n == k
print("n = 2, k = 2, answer ", solve(2, 2))
# 12 21 Answer = 2
print("n = 3, k = 3, answer ", solve(3, 3)) # 10
# 121
# 131
# 132
# 212
# 213
# 231
# 232
# 312
# 313
# 323


# n > k
print("n = 3, k = 2, answer ", solve(3, 2))
# 121
# 212
# Answer 2
print("n = 4, k = 2, answer ", solve(4, 2))
# 1212
# 2121
# Answer 2
print("n = 5, k = 2, answer ", solve(5, 2))
# 12121
# 21212

print("n = 4, k = 3, answer ", solve(4, 3))
# 121 23
# 131 23
# 132 3
# 212 1
# 213 12
# 231 23
# 232 3
# 312 1
# 313 12
# 323 12
#### 26 = 10 + 16


# 1212
# 2121
# 1213
# 1312
# 1313
# 1321
# 3131
# 3132
# 3231


# n < k
print("n = 2, k = 3, answer ", solve(2, 3))
# 12
# 13
# 21
# 23
# 32
# 31

print("n = 2, k = 4, answer ", solve(2, 4))
#12
# 11!
# 12
# 13
# 14
# 21
# 22!
# 23
# 24
# 31
# 32
# 33!
# 34
# 41
# 42
# 43
# 44!

# print("n = 2, k = 5, answer ", solve(2, 5))
# # 20
# 11!
# 12
# 13
# 14
# 15
# 21
# 22!
# 23
# 24
# 25
# 31
# 32
# 33!
# 34
# 35
# 41
# 42
# 43
# 44!
# 45
# 51
# 52
# 53
# 54
# 55!

print("n = 1, k = 3, answer ", solve(2, 3))
## 3
# 1
# 2
# 3

print("n = 2, k = 3, answer ", solve(2, 3))
## 6
# 1 + 23
# 2 + 31
# 3 + 12

print("n = 3, k = 3, answer ", solve(3, 3)) # 10
## 10
# 12 + 1
# 13 + 12
# 21 + 23
# 23 + 12
# 32 + 3
# 31 + 23


# 1 + 23 + 12
# 2 + 31 +
# 3 + 12


# 121
# 131
# 132
# 212
# 213
# 231
# 232
# 312
# 313
# 323


print("n = 4, k = 3, answer ", solve(4, 3))
# 121 23
# 131 23
# 132 3
# 212 1
# 213 12
# 231 23
# 232 3
# 312 1
# 313 12
# 323 12
#### 16

print("n = 4, k = 4, answer ", solve(3, 3))
# 121 + 234
# 131 + 234
# 132 + 34
# 212 + 1
# 213 + 12
# 231 + 234
# 232 + 34
# 312 + 1
# 313 + 12
# 323 + 12
# 4121
# 4131
# 4132
# 4141
# 4142
# 4143
# 4231
# 4232
# 4241
# 4242
# 4243
# 4341
# 4342
# 4343
#### 14 + 21 = 35


print("n = 3, k = 4, answer ", solve(3, 3))
# 121
# 131
# 132
# 141
# 142
# 143

# 212
# 213
# 214
# 231
# 232
# 241
# 242
# 243

# 312
# 313
# 314
# 323
# 324

# 412
# 413
# 414
# 421
# 423
# 424
# 431
# 432
# 434

## 28