Central Delannoy numbers
Flatten your method body

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    else:
        g, y, x = egcd(b % a, a)
        return (g, x - (b // a) * y, y)


can be re-written as:

def egcd(a, b):
    if a == 0:
        return (b, 0, 1)
    g, y, x = egcd(b % a, a)
    return (g, x - (b // a) * y, y)


because returning halts the function.

Use in-line 'ternary' to reduce verbosity

def modinv(a, m):
    g, x, y = egcd(a, m)
    if g != 1:
        return 0
    else:
        return x % m


should become

def modinv(a, m):
    g, x, y = egcd(a, m)
    return 0 if g != 1 else x % m


Say something meaningful when asking for input

t = raw_input()


The user sees nothing, only an hanging interpreter.

Use a main function


Python code runs faster in functions
You can use an if name ... block to avoid execution when the module is imported.


Convert directly (minor)

Do not waste lines:

n = raw_input()
n = long(n)


should become

n = long(raw_input()) # &lt;- also add a meaningful prompt

Follow naming conventions (minor)

You follow the naming conventions pretty well, just one imprecision:

Sum = 1


should be:

sum = 1


Use proper spacing (minor)

For example this line:

prod = ((n+1)%MOD * (n)%MOD)%MOD


is hard to read because all the symbols are squashed together.

Modularize more (important)

You defined two functions, that is very good, but you could do more to reduce the 35 lines of top level imperative code that is too much.

Usually each function (including main) should be no more than 10-15 lines of code.

Use doctests to for automatic testing

In Math code, automatically testing your functions each time you run the programme can be invaluable, just use something like:

import doctest

def egcd(a, b):
    """
    Meaningful description here...

    &gt;&gt;&gt; egcd(4132, 434)
    (2, -48, 457)
    """

    if a == 0:
        return (b, 0, 1)

    g, y, x = egcd(b % a, a)
    return (g, x - (b // a) * y, y)



doctest.testmod()


and the code will be tested automatically.

Tell why

I can see many calculations in your code, but why? Following which algorithm, please write this inside the docstrings of your functions.