def main1(n,tx_): mod=10**9+7 tx=[[t,x] if t==0 else [t,x-1] for t,x in tx_] tx.sort(key=lambda x:x[1]) # dp[k]:以上条件をすくなくともk個満たさない。 dp=[0]*(n+1) dp[0]=1 num0,num1=0,0 for i,(t,x) in enumerate(tx): ndp=[0]*(n+1) if t==0: # 以下条件 if x<=num0:return 0 for j in range(n): # 以上条件を少なくともj個満たさない状態の遷移 # 今まで出てきた以上条件の内j個は少なくとも満たしていない。pk<=xkとなる箇所があった。 ndp[j]+=dp[j]*(x-num0-j) ndp[j]%=mod num0+=1 else: # 以上条件 for j in range(n): if dp[j]==0:break # 以上条件を少なくともj個満たさない状態の遷移 # x+1以上を入れると以上条件を満たせる。 # x以下を入れる。 if j+1