Transformation of the Spiritual Tree

You are given three integers a, b and h. Initially, a magical tree has the form of a full a-ary tree with height \(10^{10^{10^{10}}}\) (the height is defined as the number of edges on the path from the root to a leaf). Due to a corrupting force the tree can only maintain a form of a full b-ary tree of exact height \(h\).

To transform its shape, the tree can use two types of magic exactly:

• Removal Magic (\(\mathcal{R}\)): Select an edge \(u\to v\) (where \(u\) is the parent of \(v\)) and remove that edge as well as the entire subtree rooted at \(v\).
• Reattachment Magic (\(\mathcal{A}\)): Select an edge \(u\to v\) (where \(u\) is the parent of \(v\)) and a node \(w\) (which is not in the subtree rooted at \(v\) or among removed nodes) and reconnect the edge so that its endpoint at \(u\) is changed to \(w\). This magic can only be used if the number of edges on the unique path from the root to \(u\) is at most \(10^{10^{10}}\).

The objective is to use as few magic operations as possible to transform the original tree into a full b-ary tree of height \(h\). In the final shape, every internal node (i.e. every node at depth less than \(h\)) should have exactly b children and every leaf (at depth \(h\)) should have no children. Note that in the original tree, every node has exactly a children. Thus, for every node in the final tree:

• If \(a \ge b\): at an internal node, you need to remove \(a-b\) extra children, and at a leaf you need to remove all a children.
• If \(a \lt b\): at an internal node, you will have to add \(b-a\) children (using a reattachment magic) and, as before, remove all a children from a node chosen as a leaf.

Summing up, the minimum number of operations required is given by:

If \(b > 1\), let \(L = b^h \) (number of leaves in the final tree) and let \(I = \frac{b^h-1}{b-1}\) (number of internal nodes). Then the answer is:

[ \text{ans} = I \times |a-b| + L \times a \mod (10^9+7). ]

If \(b=1\) (the final tree is just a chain of \(h+1\) nodes), there are \(h\) internal nodes and one leaf, and the answer is:

[ \text{ans} = h \times (a-1) + a \mod (10^9+7). ]

</p>

Your task is to compute the answer modulo \(10^9+7\).

inputFormat

The input consists of a single line containing three space-separated integers a, b, and h.

outputFormat

Output a single integer, the minimum number of magic operations to transform the tree, taken modulo \(10^9+7\).

sample

3 2 1

7