#2556. Move

内存限制:128 MiB 时间限制:10 Sec

题目描述

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

输入格式

第一行N
第二行几个数表示集合LINK
LINK中所有数 <= 3,LINK中不会有重复元素
N <= 10^9

输出格式

 一行答案

样例

样例输入


			
6
13

样例输出


			
12

数据范围与提示

2018.3.17重新制作数据By Tangjz,原数据出错!未重测!