import sys MOD = 10**9 + 7 def main(): sys.setrecursionlimit(1 << 25) n = int(sys.stdin.readline().strip()) b_d = sys.stdin.readline().strip().split() b = int(b_d[0]) d = int(b_d[1]) if b == 0: print(0) return # Compute S_total = S(b, d) def compute_S(b, d): if b == 1: return d % MOD h = pow(d + 1, b, MOD) h = (h - 1) % MOD term1 = ( (d + 1) % MOD ) * h % MOD inv_d = pow(d, MOD - 2, MOD) term1 = term1 * inv_d % MOD term2 = (b) % MOD S = (term1 - term2) % MOD return S S_total = compute_S(b, d) # Compute sum(n, b, d) from functools import lru_cache import math @lru_cache(maxsize=None) def sum_layers(n, b, d): if b == 1: return min(n, d) % MOD if d == 0: return 0 # Check if h = (d+1)^(b-1) -1 > n # Compute (d+1)^(b-1) > n+1 if d + 1 == 1: h = 0 else: log_d_plus_1 = math.log(d + 1) log_n_plus_1 = math.log(n + 1) if (b - 1) * log_d_plus_1 > log_n_plus_1 + 1e-12: return sum_layers(n, b - 1, d) # Else, compute h = (d+1)^(b-1) -1 h = pow(d + 1, b - 1, MOD) h = (h - 1) % MOD # Compute k = min(d, n // (h+1)) k = n // (h + 1) if k > d: k = d rem = n - k * (h + 1) # Compute S(b-1, d) h_b_minus_1 = pow(d + 1, b - 1, MOD) h_b_minus_1 = (h_b_minus_1 - 1) % MOD term1 = ( (d + 1) % MOD ) * h_b_minus_1 % MOD inv_d = pow(d, MOD - 2, MOD) term1 = term1 * inv_d % MOD term2 = (b - 1) % MOD S_b_minus_1_d = (term1 - term2) % MOD sum_total = (k * ( (S_b_minus_1_d + b) % MOD )) % MOD if rem > 0: if k < d: sum_rem = sum_layers(rem, b - 1, d) else: sum_rem = sum_layers(rem, b - 1, d) sum_total = (sum_total + sum_rem) % MOD return sum_total % MOD sum_n = sum_layers(n, b, d) % MOD # Compute result result = (S_total - sum_n) % MOD print(result) if __name__ == "__main__": main()