Gambler's Dice

Problem Statement

Gambler's Dice Problem Description You are given an n-ary perfect tree with k levels. You need to mark each node of this tree with a number on dice such that the resulting tree is Gambler Friendly. A tree is Gambler Friendly if the following holds: For every node of tree, let's say it is marked with a number p (1 <= p <= 6), then every adjacent node of this tree is marked with a number q that is adjacent to p on dice. (i.e. p and q are adjacent on dice and p != q) Note: A number is not adjacent to itself on dice. You need to calculate the number of possible ways to paint the tree such that it is Gambler Friendly. Since the number can be very large, print it modulo 10 9 + 7. Examples Example 1: Input: 3 3 Output: 100663296 Constraints 2 <= n <= 10 5 1 <= k <= 10 5 Input Format: 2 space separated integers, n and k Note for reference: Following is a perfect binary tree with 4 levels.