黑妹的游戏VI
题号：NC16789
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 128 M，其他语言256 M
64bit IO Format: %lld

题目描述

黑妹在玩游戏时又遇到了一个难题，这个游戏初始时给你k个整数x，黑妹需要构建一个长度为n的数组使得该数组恰好包含这k个整数，剩下的位置将由黑妹填上一些不大于100的正整数，要求数组里任意相邻的两个整数互素。
黑妹轻松解决了这个游戏，但是她想知道具体有多少种方法构建这个数组。
由于答案可能很大，输出这个数对1000000007取模后的值。

输入描述:

)

输出描述:

输出答案对1000000007取模后的值。
示例1

输入

复制 
3 8 2

输出

复制 
50