# Solution of;
# Project Euler Problem 696: Mahjong
# https://projecteuler.net/problem=696
# 
# The game of Mahjong is played with tiles belonging to $s$ suits. Each tile 
# also has a number in the range $1\ldots n$, and for each suit/number 
# combination there are exactly four indistinguishable tiles with that suit 
# and number. (The real Mahjong game also contains other bonus tiles, but 
# those will not feature in this problem. )A winning hand is a collection of 
# $3t+2$ Tiles (where $t$ is a fixed integer) that can be arranged as $t$ 
# Triples and one Pair, where:A Triple is either a Chow or a PungA Chow is 
# three tiles of the same suit and consecutive numbersA Pung is three 
# identical tiles (same suit and same number)A Pair is two identical tiles 
# (same suit and same number)For example, here is a winning hand with $n=9$, 
# $s=3$, $t=4$, consisting in this case of two Chows, two Pungs, and one 
# Pair:Note that sometimes the same collection of tiles can be represented as 
# $t$ Triples and one Pair in more than one way. This only counts as one 
# winning hand. For example, this is considered to be the same winning hand as 
# above, because it consists of the same tiles:Let $w(n, s, t)$ be the number 
# of distinct winning hands formed of $t$ Triples and one Pair, where there 
# are $s$ suits available and tiles are numbered up to $n$. For example, with 
# a single suit and tiles numbered up to 4, we have $w(4, 1, 1) = 20$: there 
# are 12 winning hands consisting of a Pung and a Pair, and another 8 
# containing a Chow and a Pair. You are also given that $w(9, 1, 4) = 13259$, 
# $w(9, 3, 4) = 5237550$, and $w(1000, 1000, 5) \equiv 107662178 
# \pmod{1\,000\,000\,007}$. Find $w(10^8, 10^8, 30)$. Give your answer modulo 
# $1\,000\,000\,007$.
# 
# by lcsm29 http://github.com/lcsm29/project-euler
import timed


def dummy(n):
    pass


if __name__ == '__main__':
    n = 1000
    i = 10000
    prob_id = 696
    timed.caller(dummy, n, i, prob_id)
