Handshakes that don't cross (in Python)

You are given an even number n of people that stand around a circle and each person shakes hands with someone else so that there are n/2 handshakes total. Return the number of ways these handshakes could occur such that none of the handshakes cross. Since the answer could be very large, return it modulo 10^9+7. (a) Solve it using naive recursive approach. (b) Improve the naive approach using bottom-up dynamic programming approach. (c) Improve the naive approach using top-down dynamic programming approach.

(To test: input: 4, output: 2

input: 6, output: 5

input: 8, output: 14)