def to_number(a, base=10):
    result = 0
    for i in range(len(a)):
        result += a[len(a)-i-1] * base ** (i-1)
    return result

def to_polinom(a, base=10):
    result = []
    i = 0
    while a > 0:
        i += 1
        result.insert(0, a % base)
        a = a  // base
    return result

def carry_over(c, base=10):
    n = len(c)
    for i in range(n-1, 0, -1):  
        carry = c[i] // base 
        remainder = c[i] % base  
        c[i] = remainder  
        c[i - 1] += carry  

    while c[0] >= base:
        carry = c[0] // base
        c[0] %= base
        c.insert(0, carry)  
    return c
	
a = 9**67
b = 9**67

print(f"{a*b:.0f}") 


result_1 = to_polinom(a, base=10)
result_2 = to_polinom(b, base=10)

result = karatsuba(result_1, result_2, max(len(result_1),len(result_2)))
carry = carry_over(result)
number = to_number(carry , base=10)
print(f"{number:.0f}", carry)

            

		
void to_number(int* a, int length, int* result, int base = 10) {
    *result = 0;
    for (int i = 0; i < length; ++i) {
        *result += a[length - i - 1] * static_cast(pow(base, i-1));
    }
}

void to_polinom(int a, std::vector& result, int base = 10) {
    int i = 0;
    while (a > 0) {
        result[i] = a % base;  
        a = a / base;          
        i++;
    }
}

void print_large_number(const int* arr, int length) {
    int i = length - 1;
    // Пропускаем ведущие нули
    // Выводим число
    for (int i = 0; i < length; ++i) {
        std::cout << arr[i];
    }
    std::cout << std::endl;
}
  
int main() {

   
    int a[65] = { 0 };  
    int b[65] = { 0 };  

   
    a[0] = 9;  
    a[63] = 0;
    a[62] = 0;
    a[61] = 0;

   
    b[0] = 5;  
    b[63] = 0;
    b[62] = 0;
    b[61] = 0;


    int n = 65;
    int* c = new int[2 * n]();

  
    karatsuba(a, b, c, n);
    print_array(c, 2 * n);


   
    int result = 0;
    print_large_number(c, 2 * n);
    delete[] c;


    return 0;
}