<filename>743_WindowIntoAMatrix__SLOW.py
"""
<NAME>

difficulty: 10%
run time: 12m
answer: 259158998

	***

743 Window into a Matrix

A window into a matrix is a contiguous sub matrix.

Consider a 2xn matrix where every entry is either 0 or 1.
Let A(k,n) be the total number of these matrices such that the sum of the entries in every 2xk window is k.

You are given that A(3,9) = 560 and A(4,20) = 1060870.

Find A(10^8, 10^16). Give your answer modulo 1000000007.

	***

Key Observations

Every valid matrix will repeat with period k (if you allow for equivalence of 1-0 and 0-1 columns)
"""

import time
from lib.num import mod_inverse

mod = 1000000007

fact = [1]
for a in range(1, 10**8+1):
	fact.append((fact[-1] * a) % mod)

fact_inv = []
for a in fact:
	fact_inv.append(mod_inverse(a, mod))

print(f"pre-processing done ({time.strftime('%I:%M:%S %p')})")
	
def choose(a,b): 
	return (fact[a] * fact_inv[a-b] * fact_inv[b]) % mod

def solve(k, L):
	total = 0
	for ones in range(k, -1, -2):
		twos = (k - ones) // 2
		count = choose(k, ones) * choose(k - ones, twos)
		count *= pow(2, ones * L // k, mod)
		total += count
	return total % mod

assert solve(3, 9) == 560
assert solve(4, 20) == 1060870

print(solve(10**8, 10**16))
<filename>743_WindowIntoAMatrix__SLOW.py
"""
<NAME>

difficulty: 10%
run time: 12m
answer: 259158998

	***

743 Window into a Matrix

A window into a matrix is a contiguous sub matrix.

Consider a 2xn matrix where every entry is either 0 or 1.
Let A(k,n) be the total number of these matrices such that the sum of the entries in every 2xk window is k.

You are given that A(3,9) = 560 and A(4,20) = 1060870.

Find A(10^8, 10^16). Give your answer modulo 1000000007.

	***

Key Observations

Every valid matrix will repeat with period k (if you allow for equivalence of 1-0 and 0-1 columns)
"""

import time
from lib.num import mod_inverse

mod = 1000000007

fact = [1]
for a in range(1, 10**8+1):
	fact.append((fact[-1] * a) % mod)

fact_inv = []
for a in fact:
	fact_inv.append(mod_inverse(a, mod))

print(f"pre-processing done ({time.strftime('%I:%M:%S %p')})")
	
def choose(a,b): 
	return (fact[a] * fact_inv[a-b] * fact_inv[b]) % mod

def solve(k, L):
	total = 0
	for ones in range(k, -1, -2):
		twos = (k - ones) // 2
		count = choose(k, ones) * choose(k - ones, twos)
		count *= pow(2, ones * L // k, mod)
		total += count
	return total % mod

assert solve(3, 9) == 560
assert solve(4, 20) == 1060870

print(solve(10**8, 10**16))
<NAME>  difficulty: 10% run time: 12m answer: 259158998  	***  743 Window into a Matrix  A window into a matrix is a contiguous sub matrix.  Consider a 2xn matrix where every entry is either 0 or 1. Let A(k,n) be the total number of these matrices such that the sum of the entries in every 2xk window is k.  You are given that A(3,9) = 560 and A(4,20) = 1060870.  Find A(10^8, 10^16). Give your answer modulo 1000000007.  	***  Key Observations  Every valid matrix will repeat with period k (if you allow for equivalence of 1-0 and 0-1 columns)