<p>On day <code>1</code>, one person discovers a secret.</p>

<p>You are given an integer <code>delay</code>, which means that each person will <strong>share</strong> the secret with a new person <strong>every day</strong>, starting from <code>delay</code> days after discovering the secret. You are also given an integer <code>forget</code>, which means that each person will <strong>forget</strong> the secret <code>forget</code> days after discovering it. A person <strong>cannot</strong> share the secret on the same day they forgot it, or on any day afterwards.</p>

<p>Given an integer <code>n</code>, return<em> the number of people who know the secret at the end of day </em><code>n</code>. Since the answer may be very large, return it <strong>modulo</strong> <code>10<sup>9</sup> + 7</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 6, delay = 2, forget = 4
<strong>Output:</strong> 5
<strong>Explanation:</strong>
Day 1: Suppose the first person is named A. (1 person)
Day 2: A is the only person who knows the secret. (1 person)
Day 3: A shares the secret with a new person, B. (2 people)
Day 4: A shares the secret with a new person, C. (3 people)
Day 5: A forgets the secret, and B shares the secret with a new person, D. (3 people)
Day 6: B shares the secret with E, and C shares the secret with F. (5 people)
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 4, delay = 1, forget = 3
<strong>Output:</strong> 6
<strong>Explanation:</strong>
Day 1: The first person is named A. (1 person)
Day 2: A shares the secret with B. (2 people)
Day 3: A and B share the secret with 2 new people, C and D. (4 people)
Day 4: A forgets the secret. B, C, and D share the secret with 3 new people. (6 people)
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= n &lt;= 1000</code></li>
	<li><code>1 &lt;= delay &lt; forget &lt;= n</code></li>
</ul>

class Solution:
    def peopleAwareOfSecret(self, n: int, delay: int, forget: int) -> int:
        # on day 1 1 person know
        # if delay is non-zero, then only one person knows
        # if forget > 0, then increment by n_knows
        # if forget becomes 0 then decrement n_knows by 1?
        # who is forgetting
        # who is spreading
        # dp[2] = dp[1] + n_spreading - n_forgetting

        memo = {1: 1}
        for i in range(2, n + 1):
            new_memo = {}
            # print(f"day_prev={i}, memo={memo}")
            for j in range(2, i + 1):
                
                if j > forget:
                    new_memo[j] = 0
                else:
                    if j > delay:
                        # ppl start spreading
                        new_memo[j] = memo[j - 1]
                        if 1 in new_memo:
                            new_memo[1] += new_memo[j]
                        else:
                            new_memo[1] = new_memo[j]
                    else:
                        # these folks continue knowing
                        new_memo[j] = memo.get(j-1, 0)
            # print(f"day={i}, memo={new_memo}")
            memo = new_memo
        print(memo)
        return sum(memo.values()) % (1000000000 + 7)

        
625