I encountered this question in undergrad intro combinatorics class and my professor showed us how to use generating expressions to get the answer (it should be 1061).

My question has two parts:

1. Is there anyway to solve this problem from first principles without generating expressions? (I'm not looking for some complicated analytic expression, but an actual exact result)
2. Using generating expressions, what's the *intuition* behind each step of the process of solving?

I realize this is a bulky question, so please feel free to answer either part (or both) in full or just leave whatever thoughts you may have.