This page is still under construction.

Parts of this page are still being built. What you see may change.

Hexagon travel

Time limit2sMemory limit32 MB

Summary
Count the orders of L left turns, R right turns and M moves that leave a hex-grid robot on a red, green, or blue tile, modulo 1,000,000,007.
Level

Hard8 of 10

Topics
Dynamic programming, Combinatorics, Math, Geometry
Solved
No attempts yet

Problem

A board is built from hexagonal tiles joined like a honeycomb. Each tile is painted red, green, or blue, and two tiles that share an edge must have different colors. Among the colorings that satisfy this rule, the board below is the one in use.

A robot sits at the exact center of one of the blue tiles, facing right. The robot takes three commands: LEFT, RIGHT, and MOVE. To define them precisely, number the directions a robot at the center of a tile can face from 0 to 5 as in the picture below. At the start the robot faces right, which is direction 0.

  • LEFT: if the robot faces direction xx, it faces direction x−1x-1 after the command. If xx was 0, the new direction is 5.
  • RIGHT: if the robot faces direction xx, it faces direction x+1x+1 after the command. If xx was 5, the new direction is 0.
  • MOVE: the robot crosses one edge in the direction it faces and stops at the center of the neighboring tile. The direction it faces stays the same.

The order of the commands is not fixed yet, but the counts are: the robot performs LEFT LL times, RIGHT RR times, and MOVE MM times. So the number of distinct command orders the robot can perform is

(L+R+M)!L! R! M!\frac{(L+R+M)!}{L!\,R!\,M!}

Given LL, RR, and MM, write a program that counts the orders leaving the robot on a red tile, the orders leaving it on a green tile, and the orders leaving it on a blue tile.

Input

The first line contains the number of LEFT commands LL, the number of RIGHT commands RR, and the number of MOVE commands MM, separated by spaces. (0≤L,R,M≤20000 \le L, R, M \le 2000)

Output

Print three lines. The first line holds the number of orders that end on a red tile, the second line the number that end on a green tile, and the third line the number that end on a blue tile. The answers can be very large, so print all three modulo 1,000,000,007.

Examples2

  1. Example 1

    Input
    1 1 2
    
    Expected output
    2
    6
    4
    
  2. Example 2

    Input
    0 0 0
    
    Expected output
    0
    0
    1