109 - ZOJ Monthly, September 2011 - J
In Summer 2011, the ZJU-ICPC Team has a n-days training schedule. ZJU-ICPC Team has been divided into 4 Group: Akiba, BiliBili, CIA, Double(Group A, B, C, D). There is a group in charge of the training problems on each day. As the ICPC Team manager, you have to decide which team is in charge of the problems on each day. But there are something you should rememeber:
1. No team is able to provide problems on two adjacent days.
How many ways are there to arrange the schedule? Output the answer modulo 1000000007.
There are multiple test cases(less than 50).
Each case contains two integers n, m (1 ≤ n ≤ 10000000, 0 ≤ m ≤ 10),
which indicate the number of days in Summer 2011 and the number of days that have been decided.
For each case, output a single line containing the answer, the number of the ways to arrange the schedule modulo 1000000007.
3 2 1 A 3 C 2 1 1 D
Case 1: 2 ways: ABC, ADC. Case 2: 3 ways: DA, DB, DC.
Author: Liang, Jiaxing