Young Bojan, today a successful student of electrical engineering, loved coloring ever since he was a little boy. Remembering careless days from his childhood, he decided to buy a coloring book and K colors and get to work. It’s interesting that Bojan doesn’t like colorful pictures, so he decided to color each picture using at most three different colors. Additionally, Bojan will never color two adjacent areas using the same color because, as he puts it, "what’s the use of this line in between then?" Two areas are considered adjacent if their edges have at least one joint point. For example, areas denoted with 4 and 3 (see image below) are adjacent, whereas areas 1 and 2 aren’t. Additionally, coloring of the image below is in accordance with all of Bojan’s demands.
Before he begins coloring a picture, Bojan asks himself in how many ways he can color that picture so he meets with all his conditions. Given the fact that Bojan is studying electrical engineering, it is understandable that combinatorics isn’t his strong point, so he asked you for help.
You can find the coloring book with the numbered pictures on the next page.
입력 2 2 출력 0 입력 5 3 출력 12 입력 7 3 출력 96
출처:2013-2014 contest7 4/6