← 返回 optiver 的题目列表Count Valid Stock Transaction Sequences
类型：online_judge
Given three non-negative integers n, k, and m:
You initially own k shares of stock.
On each day, you may make at most one transaction:
buy one share, or
sell one share.
Your number of shares must never become negative.
Count the number of valid transaction sequences that leave you with exactly n shares after at most m days.
Different transaction orders are different sequences. A sequence of zero transactions is allowed, so when k == n, the empty sequence counts.
Input
One line containing three integers:
n k m
Output
Print the total number of valid transaction sequences.
Example
Input
2 1 3
Output
4
The valid sequences are:
buy
buy, sell, buy
buy, buy, sell
sell, buy, buy
The original prompt does not specify constraints or a modulo. Return the exact integer count.
Example
Input
2 1 3
Output
4