Counting Strict n-ary Trees

A strict n‑ary tree is defined as a tree in which every non‐leaf node has exactly \(n\) children. The depth of a tree is defined as the maximum level of any node with the root at level 0. In other words, if the deepest node in the tree is at level \(d\), then the tree is said to be of depth \(d\).

For example, a strict 2‑ary tree of depth 2 has exactly 3 distinct structures.

Let the number of strict n‑ary trees of depth at most \(m\) be defined recursively as follows:

[ f(0)=1, \quad f(m)=1+(f(m-1))^n, \quad m\ge 1. ]

Then the number of strict n‑ary trees of depth exactly \(d\) is:

[ T(d)=\begin{cases} 1, & d=0,\ f(d)-f(d-1), & d\ge 1. \end{cases} ]

Given \(n\) and \(d\), count the number of strict n‑ary trees of depth exactly \(d\).

inputFormat

The input consists of a single line containing two integers \(n\) and \(d\) separated by whitespace, where \(n\) is the number of children required for every non‑leaf node and \(d\) is the depth of the tree.

outputFormat

Output a single integer representing the number of strict n‑ary trees of depth exactly \(d\).

sample

2 0

1