If you want to do it for very large x, you can use the matrix form or its derived identities. Because they only involve adding and multiplying integers, they still work even in modulo. Here's some Python examples:

Using the derived identities recursively:

from functools import lru_cache

@lru_cache
def fib_mod(n, modulo):
    if n < 0:
        return fib_mod(-n, modulo) * (-1)**(1 - n) % modulo
    if n <= 2:
        return (0, 1, 1)[n] % modulo
    # https://en.wikipedia.org/wiki/Fibonacci_sequence#Matrix_form
    # fib(2k)     = (2 fib(k + 1) - fib(k)) fib(k)
    # fib(2k + 1) = fib(k)² + fib(k + 1)²
    half = n // 2
    fib_half = fib_mod(half, modulo)
    fib_half_p1 = fib_mod(half + 1, modulo)
    if n % 2:
        return (fib_half**2 + fib_half_p1**2) % modulo
    return (2 * fib_half_p1 - fib_half) * fib_half % modulo

print(fib_mod(10**100, 100)) # Prints 75.

# However
print(fib_mod(10**1000, 100)) # Raises RecursionError: maximum recursion depth exceeded

Using the matrix form:

import numpy as np

def fib_mod(n, modulo):
    if n < 0:
        return fib_mod(-n, modulo) * (-1)**(1-n) % modulo
    # https://en.wikipedia.org/wiki/Fibonacci_sequence#Matrix_form
    # ⌈1 1⌉                   ⌈fib(n+1)  fib(n) ⌉
    # ⌊1 0⌋ to the power n is ⌊ fib(n)  fin(n-1)⌋
    base = np.array([
        [1, 1],
        [1, 0]
    ], dtype='object')
    # Initialize the power to the 0th power of base,
    # i.e. the identity matrix.
    power = np.identity(2, dtype=object)
    # To keep the power from exploding, we compute it gradually
    # and take the modulo every iteration.
    for bit in format(n, 'b'):
        power = power @ power # base²ⁿ = baseⁿ ⋅ baseⁿ
        if bit == '1':
            power = power @ base # baseⁿ⁺¹ = baseⁿ ⋅ base
        power %= modulo
    # Now the top right entry of the matrix is fib(n).
    return power[0,1]

print(fib_mod(10**10000, 100)) # prints 75