Yet another build array problem - MarisaOJ: Marisa Online Judge

Yet another build array problem

Time limit: 1000 ms
Memory limit: 256 MB
How many arrays $A$ of length $n$ consisting of non-negative integers do not exceed $k$ such that the sum of every 2 adjacent elements is a prime number? ### Input - The first line contains 2 integers $n, k$. ### Output - Print the number of satisfied array modulo $10^9+7$. ### Constraints - $1 \le n \le 100$ - $1 \le k \le 1000$. ### Example Input: ``` 2 2 ``` Output: ``` 5 ``` #### Note: There are $5$ arrays: $(0, 2), (1, 1), (1, 2), (2, 1), (2, 0)$.