lego_blocks.py

# -*- coding: utf-8 -*-
"""Lego Blocks

Automatically generated by Colaboratory.

Original file is located at
    https://colab.research.google.com/drive/1b3bN-V-Vfhn0q4t72EeU4SVjzU5IcxUL
"""

def doSomething(m,n):
    #Do Something
    m= int(m)
    n= int(n)
    MOD = (10**9+7)
    row_combinations = [1,1,2,4]
    while len(row_combinations)<=m:
        row_combinations.append(sum(row_combinations[-4:])%MOD)
    total = [pow(c,n,MOD) for c in row_combinations]
    unstable = [0,0]
    for i in range(2,m+1):
        f=lambda j:(total[j] -unstable[j]) * total[i-j]
        result = sum(map(f,range(1,i)))
        unstable.append(result%MOD)

    return (total[m]-unstable[m])%MOD
inputVal1 = input()
inputVal2 = input()
outputVal = doSomething(inputVal1,inputVal2)
print(outputVal)