Description

For a recursive function $w(a,b,c)$:

• If $a \le 0$ or $b \le 0$ or $c \le 0$, return $1$.
• If $a>20$ or $b>20$ or $c>20$, return $w(20,20,20)$.
• If $a<b$ and $b<c$, return $w(a,b,c-1)+w(a,b-1,c-1)-w(a,b-1,c)$.
• Otherwise, return $w(a-1,b,c)+w(a-1,b-1,c)+w(a-1,b,c-1)-w(a-1,b-1,c-1)$.

This is a simple recursive function, but implementing it naively may cause issues. When $a, b, c$ are all $15$, the number of calls becomes very large. You need to find a way to handle this efficiently.

Note: For example, $w(30,-1,0)$ satisfies both condition 1 and condition 2. Evaluate according to the earliest condition listed above. The answer is $1$.

Input Format

Multiple lines of input. Each line contains three integers $a, b, c$.

The input ends with $-1,-1,-1$.

Output Format

Output multiple lines. Each line should be in the format:

w(a, b, c) = ans

Mind the spaces.

1 1 1
2 2 2
-1 -1 -1

w(1, 1, 1) = 2
w(2, 2, 2) = 4

Hint

Constraints

• Each input number is an integer in $[-9223372036854775808, 9223372036854775807]$.
• The number of input lines excluding $-1, -1, -1$, denoted $T$, satisfies $1 \leq T \leq 10^5$.

Translated by ChatGPT 5