fork download 
  1. # by the authority of GOD   author: manhar singh sachdev #
  2.  
  3. import os,sys
  4. from io import BytesIO,IOBase
  5. from bisect import bisect_right as br
  6. from types import GeneratorType
  7.  
  8. def bootstrap(f,stack=[]):
  9.     def wrappedfunc(*args,**kwargs):
  10.         if stack:
  11.             return f(*args,**kwargs)
  12.         else:
  13.             to = f(*args,**kwargs)
  14.             while True:
  15.                 if type(to) is GeneratorType:
  16.                     stack.append(to)
  17.                     to = next(to)
  18.                 else:
  19.                     if len(stack):
  20.                         stack.pop()
  21.                     if not stack:
  22.                         break
  23.                     to = stack[-1].send(to)
  24.             return to
  25.  
  26.     return wrappedfunc
  27.  
  28. mod = 10**9+7
  29. fac = [1]
  30. for ii in range(1,10**5+1):
  31.     fac.append((fac[-1]*ii)%mod)
  32. fac_in = [pow(fac[-1],mod-2,mod)]
  33. for ii in range(10**5,0,-1):
  34.     fac_in.append((fac_in[-1]*ii)%mod)
  35. fac_in.reverse()
  36.  
  37. def comb(a,b):
  38.     if a < b:
  39.         return 0
  40.     return (fac[a]*fac_in[a-b]*fac_in[b])%mod
  41.  
  42. @bootstrap
  43. def find(l,r,val,inde):
  44.     if l >= r:
  45.         return 1
  46.     x = inde[val][br(inde[val],r)-1]
  47.     return (comb(r-l,x-l)*find(l,x-1,val,inde)*find(x+1,r,val+1,inde))%mod
  48.  
  49. def main():
  50.     for case in range(1,int(input())+1):
  51.         n = int(input())
  52.         v = list(map(int,input().split()))
  53.         inde = [[] for _ in range(n+1)]
  54.         for ind,i in enumerate(v):
  55.             inde[i].append(ind)
  56.         if v[0] != 1:
  57.             ans = 0
  58.         else:
  59.             for i in range(1,n):
  60.                 if v[i] > v[i-1]:
  61.                     if v[i]-v[i-1] != 1:
  62.                         ans = 0
  63.                         break
  64.             else:
  65.                 ans = find(0,n-1,1,inde)
  66.         print'Case #{}: {}'.format(case,ans)
  67.  
  68. # Fast IO Region
  69. BUFSIZE = 8192
  70.  
  71. class FastIO(IOBase):
  72.     newlines = 0
  73.  
  74.     def __init__(self,file):
  75.         self._fd = file.fileno()
  76.         self.buffer = BytesIO()
  77.         self.writable = "x" in file.mode or "r" not in file.mode
  78.         self.write = self.buffer.write if self.writable else None
  79.  
  80.     def read(self):
  81.         while True:
  82.             b = os.read(self._fd,max(os.fstat(self._fd).st_size,BUFSIZE))
  83.             if not b:
  84.                 break
  85.             ptr = self.buffer.tell()
  86.             self.buffer.seek(0,2),self.buffer.write(b),self.buffer.seek(ptr)
  87.         self.newlines = 0
  88.         return self.buffer.read()
  89.  
  90.     def readline(self):
  91.         while self.newlines == 0:
  92.             b = os.read(self._fd,max(os.fstat(self._fd).st_size,BUFSIZE))
  93.             self.newlines = b.count(b"\n")+(not b)
  94.             ptr = self.buffer.tell()
  95.             self.buffer.seek(0,2),self.buffer.write(b),self.buffer.seek(ptr)
  96.         self.newlines -= 1
  97.         return self.buffer.readline()
  98.  
  99.     def flush(self):
  100.         if self.writable:
  101.             os.write(self._fd,self.buffer.getvalue())
  102.             self.buffer.truncate(0),self.buffer.seek(0)
  103.  
  104. class IOWrapper(IOBase):
  105.     def __init__(self,file):
  106.         self.buffer = FastIO(file)
  107.         self.flush = self.buffer.flush
  108.         self.writable = self.buffer.writable
  109.         self.write = lambda s:self.buffer.write(s.encode("ascii"))
  110.         self.read = lambda:self.buffer.read().decode("ascii")
  111.         self.readline = lambda:self.buffer.readline().decode("ascii")
  112.  
  113. sys.stdin,sys.stdout = IOWrapper(sys.stdin),IOWrapper(sys.stdout)
  114. input = lambda:sys.stdin.readline().rstrip("\r\n")
  115. if __name__ == "__main__":
  116.     main()
Success #stdin #stdout 0.05s 77532KB
comments (?)
stdin 
3
4
1 2 2 1
3
1 1 2
3
1 1 3
stdout 
Case #1: 1
Case #2: 2
Case #3: 0
https://ideone.com/3i9fDb
language:
Python (PyPy 2.7.13)
created:
3 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!