Hexagon travel
Time limit2sMemory limit32 MB
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 , it faces direction after the command. If was 0, the new direction is 5.RIGHT: if the robot faces direction , it faces direction after the command. If 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 times, RIGHT times, and MOVE times. So the number of distinct command orders the robot can perform is
Given , , and , 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 , the number of RIGHT commands , and the number of MOVE commands , separated by spaces. ()
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.