2556 - Move

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

Input

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

Output

一行答案

Examples

Input

6
13

Output

12

Hint

2018.3.17重新制作数据By Tangjz，原数据出错！未重测！

Time Limit 1 second
Memory Limit 128 MB
Discuss Stats
上一题 下一题