This Problem was given by DeadlyCritic as challenge

Statement:

Given 1369D - TediousLee solve it for $$$10^{18}$$$ without using Matrix Exponentiation.

Solution:

In order to maximize the number of Claws, the basic idea is to keep track of no. of nodes with no child at any $$$k^{th}$$$