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 resulting tree is Gambler Friendly. A tree is Gambler Friendly if following holds: For every node of tree, let 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 number of possible ways to paint tree such that it is Gambler Friendly. Since the number can be 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: 188663296 Constraints 2 <= n <= 10 5 1 <= k <= 10 5