MOD = 10**9 + 7 def main(): import sys K, L, R = map(int, sys.stdin.readline().split()) # Precompute lengths len_k and s_k (digits of k^2) # We need to compute len_k for all k up to K if K is manageable # Also, precompute s_k and the digits of k^2 for k up to K # Precompute the maximum K we might need to process for the sum/product part # But since K can be up to 1e9, we need an alternative way to compute len(K) # We first check whether len(K) >= R. If not, output -1 # To compute len(K), use the formula len(k) = 2*len(k-1) + s(k), where s(k) is the number of digits in k^2 # We'll compute len(k) if k is not very large, otherwise approximate # First, compute max possible len(k) incrementally until it exceeds R or we reach K # If K is large, like 1e9, and R is up to 1e18, len(k) = 2^(k) is way larger than 1e18 # So, for practical purposes, if k >= 60, len(k) > 1e18, but confirm for the given K and R # Function to compute len(k), s(k), and digits of k^2 precomputed = [] max_k = 0 len_k = 0 s_k = 0 digits = [] # We need a way to compute len(k) incrementally, but K can be up to 1e9, which is impossible to precompute # So, we need to compute len(k) recursively, and check if it's possible # Alternatively, since len(k) grows exponentially, for k where 2^{k-1} > R, len(k) is obviously >= 2^{k-1} > R # So, first compute 2^{k-1} and see if it's larger than R. Otherwise, compute len(k) # But calculating 2^(k-1) for k=1e9 is impossible, so we need a mathematical approach # So, we need to compute the minimal k where 2^{k-1} exceeds R, then if K >= that minimal k, len(K) > R import math def compute_min_k(R_val): if R_val == 0: return 0 return math.floor(math.log2(R_val)) + 2 minimal_k = compute_min_k(R) if K >= minimal_k: len_K_is_larger = True else: # Need to compute actual len(K) # Compute len array up to K len_array = [0] * (K + 1) s_array = [0] * (K + 1) digits_dict = {} len_array[1] = 1 s_array[1] = 1 digits_dict[1] = ['1'] for k in range(2, K+1): k_sq = k * k s = len(str(k_sq)) s_array[k] = s digits_dict[k] = list(map(int, str(k_sq))) len_array[k] = 2 * len_array[k-1] + s if len_array[k] > 1e18 * 2: break # No need to compute further as it's beyond any possible R len_K = len_array[K] if len_K < R: print(-1) return else: len_K_is_larger = True # Now, compute sum and product from L to R for f(K) # We need a recursive approach to compute the digits # Precompute len(k), s(k), digits for k up to a certain K (if K is small) # Otherwise, K is up to 60 and R is up to 1e18 # However, for K up to 60, precompute necessary data # Precompute necessary data (len, s, digits) for all k up to K # Now compute data for all k from 1 to K # Since K can be up to 1e9, but if K >= minimal_k (like 60), we can assume len(K) >= R # So, handle cases where K < minimal_k, compute data up to K # Compute len(k) for k up to minimal_k or K, whichever is smaller max_k_to_compute = min(K, minimal_k) len_array = [] s_array = [] digits_dict = {} len_k = 0 for k in range(1, max_k_to_compute +1): if k == 1: len_k = 1 s_k_val = 1 digits = ['1'] else: k_sq = k * k s_k_val = len(str(k_sq)) digits = list(map(int, str(k_sq))) len_k = 2 * len_array[k-1 -1] + s_k_val # assuming len_array is 0-based len_array.append(len_k) s_array.append(s_k_val) digits_dict[k] = digits # Now, compute if actual len(K) >= R if K > max_k_to_compute: # len(K) is definitely >= R pass else: len_K_val = len_array[K-1] # assuming 0-based if len_K_val < R: print(-1) return # Now, process the range [L, R] # We need a recursive function to compute the sum and product for positions in f(k) memo = {} def get_digits(k): if k in digits_dict: return digits_dict[k] else: k_sq = k * k digits = list(map(int, str(k_sq))) return digits def compute_len(k): if k == 0: return 0 if k == 1: return 1 if k <= len(len_array): return len_array[k-1] # assuming len_array is 0-based for k starting 1 # else, compute using the recursive formula, but this is not feasible for large k # however, this should not be necessary here since k <= max_k_to_compute def helper(k, L, R): if L > R: return (0, 1) if k == 1: if L <=1 <= R: return (1, 1) else: return (0, 1) # Get len of f(k-1) len_prev = compute_len(k-1) s_k_val = len(str(k*k)) digits = get_digits(k) mid_start = len_prev + 1 mid_end = len_prev + s_k_val # Define regions: a_L = L a_R = min(R, len_prev) left_sum = 0 left_prod = 1 if a_L <= a_R: s, p = helper(k-1, a_L, a_R) left_sum += s left_prod = (left_prod * p) % MOD mid_sum = 0 mid_prod = 1 b_L = max(L, mid_start) b_R = min(R, mid_end) if b_L <= b_R: start_pos = b_L - mid_start end_pos = b_R - mid_start for i in range(start_pos, end_pos +1): d = digits[i] if d == 0: mid_sum += 10 mid_prod = (mid_prod * 10) % MOD else: mid_sum += d mid_prod = (mid_prod * d) % MOD right_sum = 0 right_prod = 1 c_L = max(L, mid_end +1) c_R = R if c_L <= c_R: offset = mid_end new_L = c_L - offset new_R = c_R - offset s, p = helper(k-1, new_L, new_R) right_sum += s right_prod = (right_prod * p) % MOD total_sum = left_sum + mid_sum + right_sum total_prod = (left_prod * mid_prod) % MOD total_prod = (total_prod * right_prod) % MOD return (total_sum, total_prod) # Since K might be larger than max_k_to_compute but minimal_k is small, adjust K to min(K, minimal_k) effective_k = min(K, minimal_k) sum_total, product_total = helper(effective_k, L, R) print(sum_total, product_total % MOD) if __name__ == '__main__': main()