Score : 1100 points
Alice, Bob and Charlie are playing Card Game for Three, as below:
a
, b
or c
written on it. The orders of the cards in the decks cannot be rearranged.a
, Alice takes the next turn.)There are 3^{N+M+K} possible patters of the three player's initial decks. Among these patterns, how many will lead to Alice's victory?
Since the answer can be large, print the count modulo 1\,000\,000\,007 (=10^9+7).
The input is given from Standard Input in the following format:
N M K
Print the answer modulo 1\,000\,000\,007 (=10^9+7).
1 1 1
17
a
, then Alice will win regardless of Bob's and Charlie's card. There are 3×3=9 such patterns.b
, Alice will only win when Bob's card is a
, or when Bob's card is c
and Charlie's card is a
. There are 3+1=4 such patterns.c
, Alice will only win when Charlie's card is a
, or when Charlie's card is b
and Bob's card is a
. There are 3+1=4 such patterns.Thus, there are total of 9+4+4=17 patterns that will lead to Alice's victory.
4 2 2
1227
1000 1000 1000
261790852