Yet another build array problem - MarisaOJ: Marisa Online Judge

How many arrays

A

$A$ of length

n

$n$ consisting of non-negative integers do not exceed

k

$k$ such that the sum of every 2 adjacent elements is a prime number? ### Input - The first line contains 2 integers

n, k

$n, k$ . ### Output - Print the number of satisfied array modulo

10^{9} + 7

$10^9+7$ . ### Constraints -

1 \leq n \leq 100

$1 \le n \le 100$ -

1 \leq k \leq 1000

$1 \le k \le 1000$ . ### Example Input:

22

$2 2$

Output:

5

$5$

#### Note: There are

5

$5$ arrays:

(0, 2), (1, 1), (1, 2), (2, 1), (2, 0)

$(0, 2), (1, 1), (1, 2), (2, 1), (2, 0)$ .

Introduction to dynamic programming
	Hakurei Shrine
	Buying tickets
	Reading 2
	Longest increasing subsequence
	Jealousy
	Maximum path 2
	Fences painting
	Hall
	Knapsack 2
	Longest common subsequence
	Yet another build array problem
	Rectangle cutting
	Palindrome query
	Marisa
	Merging elements
	Brewing potion 8

Topic

Math

Dynamic Programming

Rating

1100

Solution (1)

Solution