Move

时间限制:10s    【提交】    空间限制:128MB

题目描述

    懒得写背景了,给你N个点构成的简单无向图G,点从0 sim N-1,给一个集合LINK
    
    点a,b有边当且仅当  存在x属于LINK使得a - b = x(mod N)
    求这个图从点0出发,经过每个点一次且仅一次,又回到点0的路径数。
    
    请输出结果 bmod 10^9+9


输入格式

    第一行N
    
    第二行几个数表示集合LINK
   


输出格式

 一行答案
  


样例输入

    6
    
     1 3
    
     

样例输出

  12
   
   

提示

  10 % 的数据 N <= 10
   
    40 %的数据,LINK中所有数 <= 2
   
    100 %的数据,LINK中所有数 <= 3,LINK中不会有重复元素
   
    100 %的数据,N <= 10^9


题目来源

Ctsc模拟赛By 洁妹