Median sequence#348
A sequence of integers of length , which consists of two elements and does not decrease (i.e., is non-decreasing or remains constant), is called a median sequence (of the -st order) if there exists an integer sequence of length N + 1 such that, for every with 1 \leq i \leq N, the equality holds: a_i = \frac{b_i + b_{i + 1}}{2}.
If the sequence is itself a median sequence of another sequence (that is, it is also a non-decreasing sequence of integers), and that sequence, is of length N + 2, then will be called a median sequence of order for . Similarly, we can define the median sequence of order .
Given a non-decreasing integer sequence with two elements and a natural number , find how many non-decreasing integer sequences exist for which the initial sequence is a median sequence of order .
The first line contains two integers a_1 and a_2 ( -20 \leq a_1 \leq a_2 \leq 20 ), which define the initial two-element sequence.
The second line contains a natural number (1 \leq k \leq 20) — the order of the median sequence.
Print a single integer — the number of non-decreasing integer sequences for which \{a_1, a_2\} is a median sequence of order .
Example 1