You are given an even number of people numPeople that stand around a circle and each person shakes hands with someone else so that there are numPeople / 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 modulo10<sup>9</sup> + 7.
class Solution: # Time: O(n^2) # Space: O(n) def number_of_ways(self, num_people: int) -> int: mod = 10**9 + 7 dp = [0] * (num_people + 1) dp[0] = 1 for people in range(2, num_people + 1, 2): total = 0 for left in range(0, people, 2): total += dp[left] * dp[people - left - 2] dp[people] = total % mod return dp[num_people]
