Problem:
Problem A: Alien's Counting Natsuki and her friends were taken to the space by an alien and made friends with a lot of aliens. During the space travel, she discovered that aliens’ hands were often very different from humans’. Generally speaking, in a kind of aliens, there are N fingers and M bend rules on a hand. Each bend rule describes that a finger A always bends when a finger B bends. However, this rule does not always imply that the finger B bends when the finger A bends. When she were counting numbers with the fingers, she was anxious how many numbers her alien friends can count with the fingers. However, because some friends had too complicated rule sets, she could not calculate those. Would you write a program for her? Input  N M  S 1  D 1  S 2  D 2 . . .  S M  D M  The first line contains two integers N and M (1 ≤ N ≤ 1000, 0 ≤ M ≤ 1000) in this order. The following M lines mean bend rules. Each line contains two integers S i and D i in this order, which mean that the finger D i always bends when the finger S i bends. Any finger appears at most once in S . Output Calculate how many numbers her alien friends can count with the fingers. Print the answer modulo 1000000007 in a line. Sample Input 1 5 4
2 3
3 4
4 3
5 4 Output for the Sample Input 1 10 Sample Input 2 5 5
1 2
2 3
3 4
4 5
5 1 Output for the Sample Input 2 2 Sample Input 3 5 0 Output for the Sample Input 3 32

Solution (Python):
import sys

def func(d, S, D):
    if S[d] == []:
        return 2, [d]
    else:
        tmp = 1
        used=[d]
        for k in S[d]:
            ret = func(k,S,D)
            tmp *= ret[0]
            used += ret[1]
        return tmp+1 , used

sys.setrecursionlimit(100000)
N,M=map(int,raw_input().split())
S=[[] for i in range(N)]
D=[-1 for i in range(N)]
for i in range(M):
    s,d=map(lambda x: int(x)-1 ,raw_input().split())
    D[s] = d
    S[d].append(s)

unevaled=range(N)
bans=[]
while(len(unevaled)>0):
    
    tmp=unevaled[0]
    T=[tmp]
    while (1):
        if D[tmp]==-1:
            root=tmp
            break
        elif D[tmp] in T:
            root=D[tmp]
            D[root]=-1
            rebase=T[ T.index(root) : ]
            Stmp=[]
            for r in rebase:
                for rs in S[r]:
                    if rs not in rebase:
                        D[rs]=root
                        Stmp.append(rs)
                if r!=root:
                    unevaled.remove(r)
            S[root]=Stmp[:]
            break
        else:
            tmp=D[tmp]
            T.append(tmp)
    b = func(root, S, D)
    bans.append(b[0])
    for r in b[1]:
        unevaled.remove(r)
ans = reduce(lambda x,y: x*y, bans)
print ans%1000000007

Solution (Python):
import sys
readline = sys.stdin.readline
write = sys.stdout.write
sys.setrecursionlimit(10**6)
def scc(N, G, RG):
    order = []
    used = [0]*N
    group = [None]*N
    def dfs(s):
        used[s] = 1
        for t in G[s]:
            if not used[t]:
                dfs(t)
        order.append(s)
    def rdfs(s, col):
        group[s] = col
        used[s] = 1
        for t in RG[s]:
            if not used[t]:
                rdfs(t, col)
    for i in range(N):
        if not used[i]:
            dfs(i)
    used = [0]*N
    label = 0
    for s in reversed(order):
        if not used[s]:
            rdfs(s, label)
            label += 1
    return label, group

def construct(N, G, label, group):
    G0 = [set() for i in range(label)]
    GP = [[] for i in range(label)]
    for v in range(N):
        lbs = group[v]
        for w in G[v]:
            lbt = group[w]
            if lbs == lbt:
                continue
            G0[lbs].add(lbt)
        GP[lbs].append(v)
    return G0, GP

N, M = map(int, readline().split())
G = [[] for i in range(N)]
RG = [[] for i in range(N)]
for i in range(M):
    s, d = map(int, readline().split()); s -= 1; d -= 1
    G[d].append(s)
    RG[s].append(d)

N0, group = scc(N, G, RG)
G0, GP = construct(N, G, N0, group)

deg = [0]*N0
for v in range(N0):
    for w in G0[v]:
        deg[w] += 1
MOD = 10**9 + 7
def dfs(v):
    r = 1
    for w in G0[v]:
        r = r * dfs(w) % MOD
    return r + 1
ans = 1
for v in range(N0):
    if deg[v] == 0:
        ans = ans * dfs(v) % MOD
write("%d\n" % ans)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**13
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    rr = []

    def f(n,m):
        a = [LI_() for _ in range(m)]
        p = collections.defaultdict(list)
        c = collections.defaultdict(list)
        for s,d in a:
            p[s].append(d)
            c[d].append(s)

        v = collections.defaultdict(int)
        d = collections.defaultdict(lambda: -1)
        b = collections.defaultdict(set)
        def _f(i):
            
            if v[i] == 2:
                return -1
            if v[i] == 1:
                d[i] = i
                b[i].add(i)
                return i
            v[i] = 1
            for j in p[i]:
                r = _f(j)
                if r < 0:
                    continue
                d[i] = r
                b[r].add(i)
            v[i] = 2
            if d[i] == i:
                return -1
            return d[i]

        for i in range(n):
            _f(i)

        def g(i):
            
            if d[i] >= 0 and d[i] != i:
                return 1
            cs = set(c[i])
            if d[i] == i:
                for j in b[i]:
                    cs |= set(c[j])
            r = 1
            
            for j in cs:
                if j in b[i]:
                    continue
                gr = g(j)
                
                r *= gr
                r %= mod
            r += 1
            return r

        r = 1
        for i in range(n):
            if d[i] == i or len(p[i]) == 0:
                gr = g(i)
                
                r *= gr
                r %= mod

        return r

    while 1:
        n,m = LI()
        if n == 0:
            break
        rr.append(f(n,m))
        break

    return '\n'.join(map(str, rr))


print(main())