#128Medium
Combinations and the number of calls
Time: 1 s · Memory: 256 MB
- Recursion
Statement
is the number of ways to choose items out of . It is computed recursively by Pascal's rule:
C(n, k):
if k == 0 or k == n: return 1
return C(n - 1, k - 1) + C(n - 1, k)
Find and how many times in total this function is called (the first call counts too).
Input format
A single line with and ().
Output format
A single line with two numbers: and the number of calls.
Examples
Input
4 2
Output
6 11
Input
5 0
Output
1 1
Note
: C(4,2) → C(3,1), C(3,2); C(3,1) → C(2,0), C(2,1); C(2,1) → C(1,0), C(1,1); C(3,2) gives the same calls. In total calls, and . Count with a global counter.
