Find the number of leaf nodes in a full k-ary tree of height m.
Note: You have to return the answer module 10^{9}+7.
 
Example 1:
Input:
k = 2, m = 2
Output:
4
Explanation:
A full Binary tree of height 2 has 4 leaf nodes. 
Example 2:
Input:
k = 2, m = 1
Output:
2
Explanation:
A full Binary tree of height 1 has 2 leaf nodes.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function karyTree() which takes 2 Integers k, and m as input and returns the number of leaf nodes in a full k-ary Tree.
 
Expected Time Complexity: O(log(m))
Expected Auxiliary Space: O(1)
 
Constraints:
1 <= k,m <= 10^{8}

Difficulty: EASY
Tags: Tree algorithms

Data structures
Skill types: Data structures
Expected Time Complexity: O(log(m))
Expected Auxiliary Space: O(1)

Starter code:

class Solution:
    def karyTree(self, k, m):
        # code here

Solutions:
class Solution:

	def karyTree(self, k, m):
		ans = 1
		l = 1000000007
		while m > 0:
			if m % 2 != 0:
				ans = ans % l * (k % l)
			m = m >> 1
			k = k % l * (k % l)
		return ans % l


class Solution:

	def karyTree(self, k, m):
		return pow(k, m, 1000000007)


import math

class Solution:

	def karyTree(self, k, m):
		return int(pow(k, m, 1000000007))


class Solution:

	def karyTree(self, k, m):
		a = 1
		mod = 10 ** 9 + 7
		while m > 1:
			if m % 2:
				m -= 1
				a *= k
			m = m // 2
			k = k ** 2 % mod
		return k * a % mod


class Solution:

	def karyTree(self, k, m):
		if m == 0:
			return 1 % 1000000007
		if m == 1:
			return k % 1000000007
		a = self.karyTree(k, m // 2) % 1000000007
		if m % 2 == 0:
			return a * a % 1000000007
		else:
			return a * a * k % 1000000007


class Solution:

	def karyTree(self, k, m):
		return pow(k, m, 10 ** 9 + 7)
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		(k, m) = map(int, input().split())
		ob = Solution()
		print(ob.karyTree(k, m))


class Solution:

	def karyTree(self, k, m):
		return pow(k, m, 10 ** 9 + 7)


def expo(x, y, mod):
	if y == 1:
		return x % mod
	if y % 2 == 0:
		ans = expo(x, y // 2, mod) % mod
		return ans * ans % mod
	else:
		ans = expo(x, y // 2, mod) % mod
		return ans * ans * x % mod

class Solution:

	def karyTree(self, k, m):
		if k == 1:
			return m
		return expo(k, m, 10 ** 9 + 7)


class Solution:

	def karyTree(self, k, m):
		mod = 1000000000.0 + 7
		return pow(k, m, 1000000007)


class Solution:

	def karyTree(self, k, m):

		def rec(k, m):
			res = 1
			while m > 0:
				if m & 1:
					res = res * k % (10 ** 9 + 7)
				k = k * k % (10 ** 9 + 7)
				m = m >> 1
			return res
		return rec(k, m)


class Solution:

	def karyTree(self, k, m):
		if m == 1:
			return k
		result = self.karyTree(k, m // 2)
		if m % 2 == 0:
			return result * result % (10 ** 9 + 7)
		else:
			return k * (result * result) % (10 ** 9 + 7) % (10 ** 9 + 7)


class Solution:

	def power(self, x, y, p):
		res = 1
		x = x % p
		if x == 0:
			return 0
		while y > 0:
			if y & 1 == 1:
				res = res * x % p
			y = y >> 1
			x = x * x % p
		return res

	def karyTree(self, k, m):
		mod = 10 ** 9 + 7
		return self.power(k, m, mod)


MOD = int(1000000000.0 + 7)

class Solution:

	def karyTree(self, k, m):
		ans = 1
		while m:
			if m & 1:
				ans = ans * k % MOD
			k = k * k % MOD
			m >>= 1
		return ans


class Solution:

	def karyTree(self, k, m):
		result = 0
		if k == 0:
			return 1
		if k == 2:
			return 2 ** m
		else:
			return pow(k, m, 1000000007)


class Solution:

	def karyTree(self, k, m):
		if m == 1 or m == 0:
			return k ** m
		c = 10 ** 9 + 7
		a = self.karyTree(k, m // 2)
		if m % 2:
			return a * a * k % c
		else:
			return a * a % c


class Solution:

	def karyTree(self, k, m):
		return pow(k, m, int(1000000000.0 + 7))


class Solution:

	def karyTree(self, k, m):
		mod = 10 ** 9 + 7
		ans = 1
		while m:
			if m & 1:
				ans = ans * k % mod
			k = k * k % mod
			m = m >> 1
		return ans


class Solution:

	def karyTree(self, k, m):
		res = 1
		mod = 1000000007
		k %= mod
		m %= mod
		while m:
			if m & 1:
				res = res * k % mod
			k = k * k % mod
			m >>= 1
		return res


class Solution:

	def exponent(self, base, power, mod):
		res = 1
		while power > 0:
			if power % 2 == 1:
				res *= base
				power -= 1
			else:
				base *= base
				base %= mod
				power //= 2
			res %= mod
		return res

	def karyTree(self, k, m):
		MOD = pow(10, 9) + 7
		return self.exponent(k, m, MOD)


class Solution:

	def karyTree(self, k, m):
		mod = 1000000007

		def fun(k, m):
			if m == 0:
				return 1
			if m == 1:
				return k
			t = fun(k, m // 2)
			if m % 2 == 0:
				return t * t % mod
			return t * t * k % mod
		return fun(k, m)


class Solution:

	def karyTree(self, k, m):
		prod = 1
		rate = k
		mod = 1000000007
		while m:
			if m & 1:
				prod = prod * rate % mod
			m >>= 1
			rate = rate * rate % mod
		return prod