m identical apples are handed out to n distinct children; a child may get none. Write distribute_apples(n: int, m: int) -> int returning the number of different distributions, mod 1_000_000_007.
distribute_apples(3, 2) # 6: (2,0,0) (0,2,0) (0,0,2) (1,1,0) (1,0,1) (0,1,1)
distribute_apples(1, 5) # 1: the only child gets everything
distribute_apples(4, 0) # 1: nobody gets anything
distribute_apples(2, 3) # 4
Constraints: 1 ≤ n ≤ 10^6, 0 ≤ m ≤ 10^6. Aim for about O(n + m).
Show hint
Picture the m apples in a row with n - 1 dividers placed among them: each arrangement of those symbols is exactly one distribution. Count the arrangements as a binomial coefficient, computed mod the prime with factorials and a modular inverse.