using System; using System.Collections.Generic; using System.Collections; using System.Collections.Specialized; using System.Linq; using System.Text; using System.IO; using System.Reflection; using static System.Math; using System.Numerics; using System.Threading; using System.Runtime.CompilerServices; static class Program{ const int mod=(int)1e9+7; const long inf=long.MaxValue-1; static List>[] li; static void Main(){ Sc sc=new Sc(); var s=sc.Ia; int n=s[0]+1,m=s[1]; li=new List>[n+1]; for(int i=1;i<=n;i++){li[i]=new List>();} for(int i=0;i0){ long t=a/b; a-=t*b;(a,b)=(b,a); u-=t*v;(u,v)=(v,u); } u%=mod; if(u<0){u+=mod;} return u%mod; } } public class Tp{ public int[] a1,a2; public bool bo=true; public Tp(List<(int,int,int)>[] li){ int n=li.Length; var b=new int[n]; a1=new int[n]; a2=new int[n-1]; var k=n-1; for(int i=n-1;i>0;i--) {if(b[i]==0){Fu(i);}} void Fu(int a) { b[a]=2; for(int i=0;i(int n,Func f){var a=new T[n];for(int i=0;i(int n,Func f){var a=new T[n];for(int i=0;i(int n,Func f){var a=new T[n];for(int i=0;i(int n,Func f){var a=new T[n];for(int i=0;i