import sys # Increase recursion depth limit for safety, although the maximum depth needed (61) is typically well below default limits. # sys.setrecursionlimit(2000) MOD = 1000000007 # Global dictionary for memoization of query results to avoid redundant computations. memo_query = {} # Global dictionary to store precomputed lengths of S(k) for k up to 61. precomputed_lengths = {} # A sentinel value slightly larger than the maximum possible R (10^18) # to indicate that the actual length exceeds 10^18. MAX_LEN = 10**18 + 1 def precompute(): """ Precomputes the lengths of S(k) for k from 0 up to 61. Stores lengths in the global `precomputed_lengths` dictionary. If a length exceeds 10^18, it's stored as MAX_LEN. This function is idempotent; it computes lengths only once. """ global precomputed_lengths # Check if already computed to avoid redundant work if 0 in precomputed_lengths: return precomputed_lengths[0] = 0 precomputed_lengths[1] = 1 for k in range(2, 62): # Compute lengths up to k=61 # Get length of S(k-1) prev_len = precomputed_lengths[k-1] # If S(k-1)'s length already exceeds the threshold, S(k)'s length will too. if prev_len >= MAX_LEN: precomputed_lengths[k] = MAX_LEN continue # Calculate k*k. Use integer type which supports large numbers. k_val = k k_squared = k_val * k_val # Calculate the number of digits in k^2. Standard library functions are efficient enough. dk2 = len(str(k_squared)) # Calculate the length of S(k) using the recursive formula: |S(k)| = 2*|S(k-1)| + d(k^2) # Python's integers handle arbitrary precision, avoiding overflow issues. new_len = 2 * prev_len + dk2 # If the calculated length exceeds 10^18, store the sentinel value MAX_LEN. if new_len > 10**18: precomputed_lengths[k] = MAX_LEN else: # Otherwise, store the exact computed length. precomputed_lengths[k] = new_len def query_middle(k, l, r): """ Computes the sum and product of digits within the specified range [l, r] (1-based indices) of the string representation of k^2. Implements the special rule where digit '0' is treated as 10 for calculations. Product is computed modulo MOD. """ k_val = k k_squared = k_val * k_val sN = str(k_squared) # Convert k^2 to string to access its digits. # Extract the relevant substring using 0-based indexing for Python slicing. # The range [l, r] is 1-based, so slice is sN[l-1 : r]. sub = sN[l-1 : r] current_sum = 0 current_prod = 1 for digit_char in sub: digit = int(digit_char) # Apply the special rule for '0'. if digit == 0: val = 10 else: val = digit # Accumulate sum. current_sum += val # Accumulate product modulo MOD. current_prod = (current_prod * val) % MOD return (current_sum, current_prod) def query(k, l, r): """ Recursively computes the sum and product of digits for the range [l, r] (1-based indices) within S(k). Uses memoization (`memo_query`) to store and retrieve results for state (k, l, r), significantly speeding up computation by avoiding recalculations. Handles the recursive structure S(k) = S(k-1) + str(k^2) + S(k-1). """ # Create state tuple for memoization lookup. state = (k, l, r) # Return cached result if available. if state in memo_query: return memo_query[state] # Base cases for recursion: # If range is invalid (l > r) or k=0 (empty sequence), return sum 0, product 1. if l > r or k == 0: return (0, 1) # Base case k=1: S(1) = "1". if k == 1: # Check if the single digit at index 1 is within the query range [l, r]. if l <= 1 <= r: result = (1, 1) # Sum 1, Product 1. else: result = (0, 1) # Index 1 is outside range. Sum 0, Product 1. # Memoize the result for this base case state. memo_query[state] = result return result # Recursive step for k > 1: # Get the precomputed length of S(k-1). len_k_minus_1 = precomputed_lengths[k-1] # Calculate k^2 and its number of digits d(k^2). k_val = k k_squared = k_val * k_val dk2 = len(str(k_squared)) # Initialize total sum and product for the current query range. total_sum = 0 total_prod = 1 # Process the three parts of S(k): S(k-1), str(k^2), S(k-1) # Part 1: Intersection with the first S(k-1) component (indices [1, len_k_minus_1]) l1 = max(l, 1) # Determine the correct upper bound r1 for the intersection. # If len_k_minus_1 is MAX_LEN, true length is > 10^18. Since r <= 10^18, min(r, true_len) = r. # If len_k_minus_1 < MAX_LEN, it's the exact length. Use min(r, len_k_minus_1). r1 = min(r, len_k_minus_1) if len_k_minus_1 < MAX_LEN else r # If the intersection range [l1, r1] is valid: if l1 <= r1: # Recursively call query for the relevant part of S(k-1). res1_sum, res1_prod = query(k-1, l1, r1) # Combine results. total_sum = (total_sum + res1_sum) # Sum accumulates normally. total_prod = (total_prod * res1_prod) % MOD # Product accumulates modulo MOD. # Part 2: Intersection with the middle str(k^2) component (indices [len_k_minus_1 + 1, len_k_minus_1 + dk2]) # This middle part computation is only needed if its start index is potentially within R's bounds. # This requires len_k_minus_1 to be less than MAX_LEN (i.e., actual length <= 10^18). if len_k_minus_1 < MAX_LEN: middle_start = len_k_minus_1 + 1 middle_end = len_k_minus_1 + dk2 l2 = max(l, middle_start) r2 = min(r, middle_end) # If the intersection range [l2, r2] is valid: if l2 <= r2: # Call query_middle for the relevant digits of str(k^2). # Adjust indices to be 1-based relative to the start of str(k^2). res2_sum, res2_prod = query_middle(k, l2 - len_k_minus_1, r2 - len_k_minus_1) # Combine results. total_sum = (total_sum + res2_sum) total_prod = (total_prod * res2_prod) % MOD # Part 3: Intersection with the second S(k-1) component (indices [len_k_minus_1 + dk2 + 1, |S(k)|]) second_part_start = len_k_minus_1 + dk2 + 1 # Get the total length of S(k), which might be MAX_LEN. len_k = precomputed_lengths[k] l3 = max(l, second_part_start) # Determine the correct upper bound r3 for the intersection. # Logic similar to r1: if len_k is MAX_LEN, effective upper bound is r. Otherwise min(r, len_k). r3 = min(r, len_k) if len_k < MAX_LEN else r # If the intersection range [l3, r3] is valid: if l3 <= r3: # Calculate the offset to convert absolute indices [l3, r3] to relative indices for S(k-1). offset = len_k_minus_1 + dk2 # Recursively call query for the relevant part of the second S(k-1). res3_sum, res3_prod = query(k-1, l3 - offset, r3 - offset) # Combine results. total_sum = (total_sum + res3_sum) total_prod = (total_prod * res3_prod) % MOD # Memoize the computed result for the state (k, l, r) before returning. memo_query[state] = (total_sum, total_prod) return (total_sum, total_prod) # Main execution logic def solve(): # Read input values K, L, R. K, L, R = map(int, sys.stdin.readline().split()) # Precompute lengths up to k=61. precompute() # Determine the effective K to use for the query. # Since S(k) for k > 61 starts with S(61), and L, R <= 10^18 < |S(61)|, # any query on S(k) for k > 61 within range [L, R] is equivalent to a query on S(61). effective_K = min(K, 61) # Get the length of S(effective_K) to check against R. length_to_check = precomputed_lengths[effective_K] # Check if R exceeds the length of S(effective_K). # This check is only necessary if the length is known exactly (not capped at MAX_LEN). # If length_to_check is MAX_LEN, it means actual length > 10^18, so R is always within bounds. if length_to_check < MAX_LEN and R > length_to_check: # If R is out of bounds, print -1 as required. print("-1") else: # If R is within bounds or the length is potentially larger than R, proceed with the query. final_sum, final_prod = query(effective_K, L, R) # Print the final computed sum and product. print(f"{final_sum} {final_prod}") # Run the main solver function. solve()