import bisect import copy import decimal import fractions import functools import heapq import itertools import math import random import sys from collections import Counter,deque,defaultdict from functools import lru_cache,reduce from heapq import heappush,heappop,heapify,heappushpop,_heappop_max,_heapify_max def _heappush_max(heap,item): heap.append(item) heapq._siftdown_max(heap, 0, len(heap)-1) def _heappushpop_max(heap, item): if heap and item < heap[0]: item, heap[0] = heap[0], item heapq._siftup_max(heap, 0) return item from math import gcd as GCD read=sys.stdin.read readline=sys.stdin.readline readlines=sys.stdin.readlines class Polynomial: def __init__(self,polynomial,max_degree=-1,eps=0,mod=0): self.max_degree=max_degree if self.max_degree!=-1 and len(polynomial)>self.max_degree+1: self.polynomial=polynomial[:self.max_degree+1] else: self.polynomial=polynomial self.mod=mod self.eps=eps def __eq__(self,other): if type(other)!=Polynomial: return False if len(self.polynomial)!=len(other.polynomial): return False for i in range(len(self.polynomial)): if self.epsself.max_degree+1: prod=prod[:self.max_degree+1] while prod and abs(prod[-1])<=self.eps: prod.pop() prod=Polynomial(prod,max_degree=self.max_degree,eps=self.eps,mod=self.mod) return prod def __truediv__(self,other): if type(other)==Polynomial: assert other.polynomial for n in range(len(other.polynomial)): if self.epsn for i in range(n): assert abs(self.polynomial[i])<=self.eps self_polynomial=self.polynomial[n:] other_polynomial=other.polynomial[n:] if self.mod: inve=MOD(self.mod).Pow(other_polynomial[0],-1) else: inve=1/other_polynomial[0] quot=[] for i in range(len(self_polynomial)-len(other_polynomial)+1): if self.mod: quot.append(self_polynomial[i]*inve%self.mod) else: quot.append(self_polynomial[i]*inve) for j in range(len(other_polynomial)): self_polynomial[i+j]-=other_polynomial[j]*quot[-1] if self.mod: self_polynomial[i+j]%=self.mod for i in range(max(0,len(self_polynomial)-len(other_polynomial)+1),len(self_polynomial)): if self.eps>bit,mod) U=[1] for _ in range(a): U.append(U[-1]*x%mod) for i in range(1<>bit,mod) U=[1] for _ in range(a): U.append(U[-1]*x%mod) for i in range(1<