В текстовом файле содержится описание ациклического ориентированного взвешенного графа.

В каждой строке файла записаны два натуральных числа (L, M) и одно положительное вещественное число (W).

L и M — номера вершин графа, W — вес ребра, ведущего из вершины L в вершину M.

Две вершины графа не могут быть соединены более чем одним ребром.

Определите и запишите в ответе количество различных путей из вершины с номером 906 в вершину с номером 293.

Существование хотя бы одного такого пути гарантируется.

Два пути считаются различными, если они проходят по разным последовательностям вершин.

Для выполнения этого задания следует написать программу.

Вершины графа могут быть пронумерованы не подряд.

L < 1000, M < 1000, W < 10 000.

Количество строк в файле не превосходит 200.

Числа в строках разделены произвольным ненулевым количеством пробелов и/или табуляций.

Типовой пример организации данных во входном файле для графа на рисунке.

100  12   1.0
6    7    7.0
6    1    1.0
1    7    5.5
7    100  2.0
4    100  8.0
1    100  12.0
1    4    2.5

При условии поиска количества различных путей из вершины 1 в вершину 100 для приведённого примера верным ответом будет 3.

Типовой пример имеет иллюстративный характер. Для выполнения задания используйте данные из прилагаемого файла

from functools import lru_cache

g = {}
for line in open('23.txt'):
    a, b, _ = map(float, line.split())
    g.setdefault(a, []).append(b)

@lru_cache(None)
def f(x, y):
    if x == y:
        return 1
    return sum(f(v, y) for v in g.get(x, ()))

print(int(f(906, 293)))

from functools import lru_cache

g = {}
for line in open('23.txt'):
    a, b, _ = map(float, line.split())
    g.setdefault(a, []).append(b)

@lru_cache(None)
def f(x, y):
    if x == y:
        return 1
    return sum(f(v, y) for v in g.get(x, ()))

from functools import lru_cache

g = {}
for line in open('23.txt'):
    a, b, _ = map(float, line.split())
    g.setdefault(a, []).append(b)

@lru_cache(None)
def f(x, y):
    if x == y:
        return 1
    return sum(f(v, y) for v in g.get(x, ()))

print(int(f(906, 293)))