using System; using System.Collections.Generic; using System.IO; using System.Linq; using System.Text; using System.Runtime.CompilerServices; using System.Runtime.InteropServices; using YukicoderContest256.Extensions; using YukicoderContest256.Questions; using System.Threading; using System.Xml.XPath; namespace YukicoderContest256.Questions { public class QuestionF : AtCoderQuestionBase { public override IEnumerable Solve(TextReader inputStream) { var (kinds, progressions, length) = inputStream.ReadValue(); var initialVector = new ModMatrix(kinds * kinds, 1); // (i, j)の数はv[ik + j]にあると定義 var transMatrix = new ModMatrix(kinds * kinds); for (int second = 0; second < kinds; second++) { initialVector[0 * kinds + second, 0] = 1; } for (int i = 0; i < progressions; i++) { var (p, q, r) = inputStream.ReadValue(); p--; q--; r--; transMatrix[q * kinds + r, p * kinds + q] = 1; } var powMatrix = transMatrix.Pow(length - 2); var counts = powMatrix * initialVector; var result = Modular.Zero; for (int previous = 0; previous < kinds; previous++) { result += counts[previous * kinds, 0]; } yield return result; } public readonly struct Modular : IEquatable, IComparable { private const int DefaultMod = 1000000007; public int Value { get; } public static int Mod { get; set; } = DefaultMod; [MethodImpl(MethodImplOptions.AggressiveInlining)] public Modular(long value) { if (unchecked((ulong)value) < unchecked((ulong)Mod)) { Value = (int)value; } else { Value = (int)(value % Mod); if (Value < 0) { Value += Mod; } } } private Modular(int value) => Value = value; public static Modular Zero => new Modular(0); public static Modular One => new Modular(1); [MethodImpl(MethodImplOptions.AggressiveInlining)] public static Modular operator +(Modular a, Modular b) { var result = a.Value + b.Value; if (result >= Mod) { result -= Mod; // 剰余演算を避ける } return new Modular(result); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static Modular operator -(Modular a, Modular b) { var result = a.Value - b.Value; if (result < 0) { result += Mod; // 剰余演算を避ける } return new Modular(result); } [MethodImpl(MethodImplOptions.AggressiveInlining)] public static Modular operator *(Modular a, Modular b) => new Modular((long)a.Value * b.Value); [MethodImpl(MethodImplOptions.AggressiveInlining)] public static Modular operator /(Modular a, Modular b) => a * Pow(b.Value, Mod - 2); // 需要は不明だけど一応 public static bool operator ==(Modular left, Modular right) => left.Equals(right); public static bool operator !=(Modular left, Modular right) => !(left == right); public static bool operator <(Modular left, Modular right) => left.CompareTo(right) < 0; public static bool operator <=(Modular left, Modular right) => left.CompareTo(right) <= 0; public static bool operator >(Modular left, Modular right) => left.CompareTo(right) > 0; public static bool operator >=(Modular left, Modular right) => left.CompareTo(right) >= 0; public static implicit operator Modular(long a) => new Modular(a); public static explicit operator int(Modular a) => a.Value; public static explicit operator long(Modular a) => a.Value; public static Modular Pow(int a, int n) { switch (n) { case 0: return Modular.One; case 1: return a; case int m when m >= 0: // ジャンプテーブル化はできなくなる var p = Pow(a, m >> 1); // m / 2 return p * p * Pow(a, m & 0x01); // m % 2 default: throw new ArgumentOutOfRangeException(nameof(n), $"べき指数{nameof(n)}は0以上の整数でなければなりません。"); } } private static List _factorialCache; private static List FactorialCache => _factorialCache ??= new List() { 1 }; private static int[] FactorialInverseCache { get; set; } const int defaultMaxFactorial = 1000000; public static Modular Factorial(int n) { if (n < 0) { throw new ArgumentOutOfRangeException(nameof(n), $"{nameof(n)}は0以上の整数でなければなりません。"); } for (int i = FactorialCache.Count; i <= n; i++) // Countが1(0!までキャッシュ済み)のとき1!~n!まで計算 { FactorialCache.Add((int)((long)FactorialCache[i - 1] * i % Mod)); } return new Modular(FactorialCache[n]); } public static Modular Permutation(int n, int r) { CheckNR(n, r); return Factorial(n) / Factorial(n - r); } public static Modular Combination(int n, int r) { CheckNR(n, r); r = Math.Min(r, n - r); try { return new Modular(FactorialCache[n]) * new Modular(FactorialInverseCache[r]) * new Modular(FactorialInverseCache[n - r]); } catch (Exception ex) when (ex is NullReferenceException || ex is ArgumentOutOfRangeException) { throw new InvalidOperationException($"{nameof(Combination)}を呼び出す前に{nameof(InitializeCombinationTable)}により前計算を行う必要があります。", ex); } } public static void InitializeCombinationTable(int max = defaultMaxFactorial) { Factorial(max); FactorialInverseCache = new int[max + 1]; var fInv = (Modular.One / Factorial(max)).Value; FactorialInverseCache[max] = fInv; for (int i = max - 1; i >= 0; i--) { fInv = (int)((long)fInv * (i + 1) % Mod); FactorialInverseCache[i] = fInv; } } public static Modular CombinationWithRepetition(int n, int r) => Combination(n + r - 1, r); private static void CheckNR(int n, int r) { if (n < 0) { throw new ArgumentOutOfRangeException(nameof(n), $"{nameof(n)}は0以上の整数でなければなりません。"); } if (r < 0) { throw new ArgumentOutOfRangeException(nameof(r), $"{nameof(r)}は0以上の整数でなければなりません。"); } if (n < r) { throw new ArgumentOutOfRangeException($"{nameof(n)},{nameof(r)}", $"{nameof(r)}は{nameof(n)}以下でなければなりません。"); } } public override string ToString() => Value.ToString(); public override bool Equals(object obj) => obj is Modular m ? Equals(m) : false; public bool Equals([System.Diagnostics.CodeAnalysis.AllowNull] Modular other) => Value == other.Value; public int CompareTo([System.Diagnostics.CodeAnalysis.AllowNull] Modular other) => Value.CompareTo(other.Value); public override int GetHashCode() => Value.GetHashCode(); } public class ModMatrix { readonly Modular[] _value; public int Height { get; } public int Width { get; } public Modular this[int row, int column] { [MethodImpl(MethodImplOptions.AggressiveInlining)] get { if (unchecked((uint)row) >= Height) ThrowsArgumentOutOfRangeException(nameof(row)); else if (unchecked((uint)column) >= Width) ThrowsArgumentOutOfRangeException(nameof(column)); return _value[row * Width + column]; } [MethodImpl(MethodImplOptions.AggressiveInlining)] set { if (unchecked((uint)row) >= Height) ThrowsArgumentOutOfRangeException(nameof(row)); else if (unchecked((uint)column) >= Width) ThrowsArgumentOutOfRangeException(nameof(column)); _value[row * Width + column] = value; } } public ModMatrix(int n) : this(n, n) { } public ModMatrix(int height, int width) { Height = height; Width = width; _value = new Modular[height * width]; } public ModMatrix(Modular[][] values) { Height = values.Length; Width = values[0].Length; _value = new Modular[Height * Width]; for (int row = 0; row < Height; row++) { var span = _value.AsSpan(row * Width, Width); values[row].AsSpan().CopyTo(span); } } public ModMatrix(Modular[,] values) { Height = values.GetLength(0); Width = values.GetLength(1); _value = new Modular[values.Length]; for (int row = 0; row < Height; row++) { var span = _value.AsSpan(row * Width, Width); for (int column = 0; column < span.Length; column++) { span[column] = values[row, column]; } } } public ModMatrix(ModMatrix matrix) { Height = matrix.Height; Width = matrix.Width; _value = new Modular[matrix._value.Length]; matrix._value.AsSpan().CopyTo(_value); } public static ModMatrix GetIdentity(int dimension) { var result = new ModMatrix(dimension, dimension); for (int i = 0; i < dimension; i++) { result._value[i * result.Width + i] = 1; } return result; } public static ModMatrix operator+(ModMatrix a, ModMatrix b) { if (a.Height != b.Height) throw new InvalidOperationException($"{nameof(a)}の行数と{nameof(b)}の行数は等しくなければなりません。"); else if (a.Width != b.Width) throw new InvalidOperationException($"{nameof(a)}の列数と{nameof(b)}の列数は等しくなければなりません。"); var result = new ModMatrix(a.Height, a.Width); for (int i = 0; i < result._value.Length; i++) { result._value[i] = a._value[i] + b._value[i]; } return result; } public static ModMatrix operator-(ModMatrix a, ModMatrix b) { if (a.Height != b.Height) throw new InvalidOperationException($"{nameof(a)}の行数と{nameof(b)}の行数は等しくなければなりません。"); else if (a.Width != b.Width) throw new InvalidOperationException($"{nameof(a)}の列数と{nameof(b)}の列数は等しくなければなりません。"); var result = new ModMatrix(a.Height, a.Width); for (int i = 0; i < result._value.Length; i++) { result._value[i] = a._value[i] - b._value[i]; } return result; } public static ModMatrix operator*(ModMatrix a, ModMatrix b) { if (a.Width != b.Height) throw new InvalidOperationException($"{nameof(a)}の列数と{nameof(b)}の行数は等しくなければなりません。"); var result = new ModMatrix(a.Height, b.Width); for (int i = 0; i < result.Height; i++) { var aSpan = a._value.AsSpan(i * a.Width, a.Width); var resultSpan = result._value.AsSpan(i * result.Width, result.Width); for (int k = 0; k < aSpan.Length; k++) { var bSpan = b._value.AsSpan(k * b.Width, b.Width); for (int j = 0; j < resultSpan.Length; j++) { resultSpan[j] += aSpan[k] * bSpan[j]; } } } return result; } public ModMatrix Pow(long pow) { if (Height != Width) throw new InvalidOperationException("累乗を行う行列は正方行列である必要があります。"); var powMatrix = new ModMatrix(this); var result = GetIdentity(Height); while (pow > 0) { if ((pow & 1) > 0) { result *= powMatrix; } powMatrix *= powMatrix; pow >>= 1; } return result; } private void ThrowsArgumentOutOfRangeException(string paramName) => throw new ArgumentOutOfRangeException(paramName); } } } namespace YukicoderContest256 { class Program { static void Main(string[] args) { IAtCoderQuestion question = new QuestionF(); var answers = question.Solve(Console.In); var writer = new StreamWriter(Console.OpenStandardOutput()) { AutoFlush = false }; Console.SetOut(writer); foreach (var answer in answers) { Console.WriteLine(answer); } Console.Out.Flush(); } } } #region Base Class namespace YukicoderContest256.Questions { public interface IAtCoderQuestion { IEnumerable Solve(string input); IEnumerable Solve(TextReader inputStream); } public abstract class AtCoderQuestionBase : IAtCoderQuestion { public IEnumerable Solve(string input) { var stream = new MemoryStream(Encoding.Unicode.GetBytes(input)); var reader = new StreamReader(stream, Encoding.Unicode); return Solve(reader); } public abstract IEnumerable Solve(TextReader inputStream); } } #endregion #region Graphs namespace YukicoderContest256.Graphs { public interface INode { public int Index { get; } } public interface IEdge where TNode : INode { TNode From { get; } TNode To { get; } } public interface IWeightedEdge : IEdge where TNode : INode { long Weight { get; } } public interface IGraph where TEdge : IEdge where TNode : INode { IEnumerable this[TNode node] { get; } IEnumerable Edges { get; } IEnumerable Nodes { get; } int NodeCount { get; } } public interface IWeightedGraph : IGraph where TEdge : IWeightedEdge where TNode : INode { } [StructLayout(LayoutKind.Auto)] public readonly struct BasicNode : INode, IEquatable { public int Index { get; } public BasicNode(int index) { Index = index; } public override string ToString() => Index.ToString(); public override bool Equals(object obj) => obj is BasicNode node && Equals(node); public bool Equals(BasicNode other) => Index == other.Index; public override int GetHashCode() => HashCode.Combine(Index); public static bool operator ==(BasicNode left, BasicNode right) => left.Equals(right); public static bool operator !=(BasicNode left, BasicNode right) => !(left == right); public static implicit operator BasicNode(int value) => new BasicNode(value); } [StructLayout(LayoutKind.Auto)] public readonly struct BasicEdge : IEdge { public BasicNode From { get; } public BasicNode To { get; } public BasicEdge(int from, int to) { From = from; To = to; } public override string ToString() => $"{From}-->{To}"; } [StructLayout(LayoutKind.Auto)] public readonly struct WeightedEdge : IWeightedEdge { public BasicNode From { get; } public BasicNode To { get; } public long Weight { get; } public WeightedEdge(int from, int to) : this(from, to, 1) { } public WeightedEdge(int from, int to, long weight) { From = from; To = to; Weight = weight; } public override string ToString() => $"{From}--[{Weight}]-->{To}"; } [StructLayout(LayoutKind.Auto)] public readonly struct GridNode : INode, IEquatable { public int Row { get; } public int Column { get; } public int Index { get; } public GridNode(int row, int column, int width) { Row = row; Column = column; Index = row * width + column; } public override string ToString() => $"({Row}, {Column})"; public override int GetHashCode() => HashCode.Combine(Row, Column, Index); public override bool Equals(object obj) => obj is GridNode node && Equals(node); public bool Equals(GridNode other) => Row == other.Row && Column == other.Column && Index == other.Index; public void Deconstruct(out int row, out int column) { row = Row; column = Column; } public static bool operator ==(GridNode left, GridNode right) => left.Equals(right); public static bool operator !=(GridNode left, GridNode right) => !(left == right); } [StructLayout(LayoutKind.Auto)] public readonly struct GridEdge : IEdge { public GridNode From { get; } public GridNode To { get; } public GridEdge(GridNode from, GridNode to) { From = from; To = to; } public override string ToString() => $"({From.Row}, {From.Column})-->({To.Row}, {To.Column})"; } public class BasicGraph : IGraph { private readonly List[] _edges; public IEnumerable this[BasicNode node] => _edges[node.Index]; public IEnumerable Edges => Nodes.SelectMany(node => this[node]); public IEnumerable Nodes => Enumerable.Range(0, NodeCount).Select(i => new BasicNode(i)); public int NodeCount { get; } public BasicGraph(int nodeCount) : this(nodeCount, Enumerable.Empty()) { } public BasicGraph(int nodeCount, IEnumerable edges) { _edges = Enumerable.Repeat(0, nodeCount).Select(_ => new List()).ToArray(); NodeCount = nodeCount; foreach (var edge in edges) { AddEdge(edge); } } public BasicGraph(int nodeCount, IEnumerable> distances) { _edges = new List[nodeCount]; int i = 0; foreach (var row in distances) { _edges[i] = new List(nodeCount); int j = 0; foreach (var distance in row) { if (distance == 1) { _edges[i].Add(new BasicEdge(i, j++)); } } i++; } } public void AddEdge(BasicEdge edge) => _edges[edge.From.Index].Add(edge); } public class WeightedGraph : IGraph { private readonly List[] _edges; public IEnumerable this[BasicNode node] => _edges[node.Index]; public IEnumerable Edges => Nodes.SelectMany(node => this[node]); public IEnumerable Nodes => Enumerable.Range(0, NodeCount).Select(i => new BasicNode(i)); public int NodeCount { get; } public WeightedGraph(int nodeCount) : this(nodeCount, Enumerable.Empty()) { } public WeightedGraph(int nodeCount, IEnumerable edges) { _edges = Enumerable.Repeat(0, nodeCount).Select(_ => new List()).ToArray(); NodeCount = nodeCount; foreach (var edge in edges) { AddEdge(edge); } } public WeightedGraph(int nodeCount, IEnumerable> distances) { _edges = new List[nodeCount]; int i = 0; foreach (var row in distances) { _edges[i] = new List(nodeCount); int j = 0; foreach (var distance in row) { _edges[i].Add(new WeightedEdge(i, j++, distance)); } i++; } } public void AddEdge(WeightedEdge edge) => _edges[edge.From.Index].Add(edge); } } #endregion #region Extensions namespace YukicoderContest256.Extensions { public static class SearchExtensions { class LowerBoundComparer : IComparer where T : IComparable { public int Compare(T x, T y) => 0 <= x.CompareTo(y) ? 1 : -1; } class UpperBoundComparer : IComparer where T : IComparable { public int Compare(T x, T y) => 0 < x.CompareTo(y) ? 1 : -1; } // https://trsing.hatenablog.com/entry/2019/08/27/211038 public static int GetGreaterEqualIndex(this ReadOnlySpan span, T inclusiveMin) where T : IComparable => ~span.BinarySearch(inclusiveMin, new UpperBoundComparer()); public static int GetGreaterThanIndex(this ReadOnlySpan span, T exclusiveMin) where T : IComparable => ~span.BinarySearch(exclusiveMin, new LowerBoundComparer()); public static int GetLessEqualIndex(this ReadOnlySpan span, T inclusiveMax) where T : IComparable => ~span.BinarySearch(inclusiveMax, new LowerBoundComparer()) - 1; public static int GetLessThanIndex(this ReadOnlySpan span, T exclusiveMax) where T : IComparable => ~span.BinarySearch(exclusiveMax, new UpperBoundComparer()) - 1; public static int GetGreaterEqualIndex(this Span span, T inclusiveMin) where T : IComparable => ((ReadOnlySpan)span).GetGreaterEqualIndex(inclusiveMin); public static int GetGreaterThanIndex(this Span span, T exclusiveMin) where T : IComparable => ((ReadOnlySpan)span).GetGreaterThanIndex(exclusiveMin); public static int GetLessEqualIndex(this Span span, T inclusiveMax) where T : IComparable => ((ReadOnlySpan)span).GetLessEqualIndex(inclusiveMax); public static int GetLessThanIndex(this Span span, T exclusiveMax) where T : IComparable => ((ReadOnlySpan)span).GetLessThanIndex(exclusiveMax); public static int BoundaryBinarySearch(Predicate predicate, int ok, int ng) { // めぐる式二分探索 while (Math.Abs(ok - ng) > 1) { int mid = (ok + ng) / 2; if (predicate(mid)) { ok = mid; } else { ng = mid; } } return ok; } public static long BoundaryBinarySearch(Predicate predicate, long ok, long ng) { while (Math.Abs(ok - ng) > 1) { long mid = (ok + ng) / 2; if (predicate(mid)) { ok = mid; } else { ng = mid; } } return ok; } public static double Bisection(Func f, double a, double b, double eps = 1e-9) { if (f(a) * f(b) >= 0) { throw new ArgumentException("f(a)とf(b)は異符号である必要があります。"); } const int maxLoop = 100; double mid = (a + b) / 2; for (int i = 0; i < maxLoop; i++) { if (f(a) * f(mid) < 0) { b = mid; } else { a = mid; } mid = (a + b) / 2; if (Math.Abs(b - a) < eps) { break; } } return mid; } } public static class StringExtensions { public static string Join(this IEnumerable source) => string.Concat(source); public static string Join(this IEnumerable source, char separator) => string.Join(separator, source); public static string Join(this IEnumerable source, string separator) => string.Join(separator, source); } public static class TextReaderExtensions { public static int ReadInt(this TextReader reader) => int.Parse(ReadString(reader)); public static long ReadLong(this TextReader reader) => long.Parse(ReadString(reader)); public static double ReadDouble(this TextReader reader) => double.Parse(ReadString(reader)); public static string ReadString(this TextReader reader) => reader.ReadLine(); public static int[] ReadIntArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(int.Parse).ToArray(); public static long[] ReadLongArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(long.Parse).ToArray(); public static double[] ReadDoubleArray(this TextReader reader, char separator = ' ') => ReadStringArray(reader, separator).Select(double.Parse).ToArray(); public static string[] ReadStringArray(this TextReader reader, char separator = ' ') => reader.ReadLine().Split(separator); // Supports primitive type only. public static T1 ReadValue(this TextReader reader) => (T1)Convert.ChangeType(reader.ReadLine(), typeof(T1)); public static (T1, T2) ReadValue(this TextReader reader, char separator = ' ') { var inputs = ReadStringArray(reader, separator); var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1)); var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2)); return (v1, v2); } public static (T1, T2, T3) ReadValue(this TextReader reader, char separator = ' ') { var inputs = ReadStringArray(reader, separator); var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1)); var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2)); var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3)); return (v1, v2, v3); } public static (T1, T2, T3, T4) ReadValue(this TextReader reader, char separator = ' ') { var inputs = ReadStringArray(reader, separator); var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1)); var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2)); var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3)); var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4)); return (v1, v2, v3, v4); } public static (T1, T2, T3, T4, T5) ReadValue(this TextReader reader, char separator = ' ') { var inputs = ReadStringArray(reader, separator); var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1)); var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2)); var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3)); var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4)); var v5 = (T5)Convert.ChangeType(inputs[4], typeof(T5)); return (v1, v2, v3, v4, v5); } public static (T1, T2, T3, T4, T5, T6) ReadValue(this TextReader reader, char separator = ' ') { var inputs = ReadStringArray(reader, separator); var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1)); var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2)); var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3)); var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4)); var v5 = (T5)Convert.ChangeType(inputs[4], typeof(T5)); var v6 = (T6)Convert.ChangeType(inputs[5], typeof(T6)); return (v1, v2, v3, v4, v5, v6); } public static (T1, T2, T3, T4, T5, T6, T7) ReadValue(this TextReader reader, char separator = ' ') { var inputs = ReadStringArray(reader, separator); var v1 = (T1)Convert.ChangeType(inputs[0], typeof(T1)); var v2 = (T2)Convert.ChangeType(inputs[1], typeof(T2)); var v3 = (T3)Convert.ChangeType(inputs[2], typeof(T3)); var v4 = (T4)Convert.ChangeType(inputs[3], typeof(T4)); var v5 = (T5)Convert.ChangeType(inputs[4], typeof(T5)); var v6 = (T6)Convert.ChangeType(inputs[5], typeof(T6)); var v7 = (T7)Convert.ChangeType(inputs[6], typeof(T7)); return (v1, v2, v3, v4, v5, v6, v7); } } } #endregion