Problem Statement

Gambler's Dice Problem Description You are given an n-ary perfect tree with k levels. Each node of this tree must be labeled with a number found on a die so that the labeled tree ends up Gambler Friendly. A tree qualifies as Gambler Friendly when the following holds: For every node in the tree, if it is labeled with a number p (1 <= p <= 6), then every node adjacent to it must be labeled with a number q that sits adjacent to p on a die. (i.e. p and q are adjacent on dice and p != q) Note: a number is not adjacent to itself on dice. Work out how many ways exist to label the tree so that it is Gambler Friendly. Since this count can grow very large, print it modulo 10 9 + 7. Input Format: 2 space separated integers, n and k Note for reference: Following is a perfect binary tree with 4 levels. Examples Example 1: Input: 3 3 Output: 100663296 Constraints 2 <= n <= 10 5 1 <= k <= 10 5