K. Alloy Factory
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Shuki is developing weapons of the future for the Wakindan army. She has created a factory line to create the alloys of the metals she wants for the weapons. She recently got a shipment of $$$v$$$ tons of vibranium and $$$s$$$ tons of steel.

Shuki arranges the metals onto her factory line by placing one ton of a specific metal into each distinct position on the line. However, Dr. Stronge was recently tweaking with some of the settings and seems to have messed up how the process works. Shuki now finds that it always takes the last two filled positions (say position $$$i$$$ and position $$$i + 1$$$ where position $$$i + 2$$$ is empty) and applies the following modification:

  • If both positions contain steel it combines the steel and turns it into vibranium and places it in position $$$i$$$.
  • For any other combination of metals, it turns the combination into steel and places it in position $$$i$$$.

If there is only one position on the line which contains an alloy, then that is the alloy that Shuki is then left with.

Help Shuki figure out how many starting arrangements of the metals (this can be quite large so you can give it modulo $$$10^{9} + 7$$$) will lead to the ending alloy being of type $$$g$$$.

Input

The first and only line of input contains $$$3$$$ space-separated integers $$$s$$$, $$$v$$$, and $$$g$$$ ($$$0 \leq s, v \leq 10^{5}$$$ and $$$s + v \geq 1$$$ and then $$$0 \leq g \leq 1$$$) representing the number of tons of vibranium, the number of tons of steel, and the goal alloy type. For conciseness, the goal alloy type will be $$$0$$$ if you want steel and $$$1$$$ if you want vibranium.

Output

Print how many starting arrangements of the metals will lead to Shuki ending up with the alloy of type $$$g$$$ (modulo $$$10^{9} + 7$$$).

Examples
Input
1 1 0
Output
2
Input
1 1 1
Output
0
Input
2 2 0
Output
4