Problem Statement

Alice's Journey Alice is planning a summer vacation across a country of n cities connected by m one-way roads. She wants to travel from her hometown (city 1 ) to the nation's capital (city n ). So that she spends enough time enjoying the scenery and roadside attractions, she insists that her trip use exactly k road segments . A trip is an ordered sequence of roads where each road starts at the city where the previous road ended, beginning at city 1 and ending at city n; the trip is allowed to pass through the same city more than once and to reuse the same road more than once. There may be several distinct roads connecting the same ordered pair of cities, and a road may lead from a city back to itself. Two trips are considered different if their sequences of roads differ in any position. Help Alice count the number of distinct valid trips of exactly k road segments from city 1 to city n. Because the answer can be very large, output it modulo 1000000007 (that is, 10^9 + 7 ). In