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

样例输出

提示

10 % 的数据 N <= 10

    40 %的数据，LINK中所有数 <= 2

    100 %的数据,LINK中所有数 <= 3,LINK中不会有重复元素

    100 %的数据,N <= 10^9

题目来源

Ctsc模拟赛By 洁妹