{"problem":{"name":"「FAOI-R2」A trip to Macao","description":{"content":"赌场贴出了如下规则（**你可以忽略没有加粗的内容**）： 1. 所有玩家在注册后方可进行游戏。 2. 活动期间，**新注册的玩家可从抽奖盒内拿走一枚筹码。抽奖盒内共 $m$ 种筹码，面值分别为 $a_1,a_2,\\ldots,a_m$ 澳元（均为正整数）**，每种一个，保证公平。 3. 本赌场仅提供一种游戏：猜拳。游戏开始时，双方各下注相同数量（以 $1$ 澳元为单位）的筹码；若猜拳分出胜负，则","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1750,"memory_limit":8192},"difficulty":{"LuoguStyle":"P5"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP10036"},"statements":[{"statement_type":"Markdown","content":"赌场贴出了如下规则（**你可以忽略没有加粗的内容**）：\n\n1. 所有玩家在注册后方可进行游戏。\n2. 活动期间，**新注册的玩家可从抽奖盒内拿走一枚筹码。抽奖盒内共 $m$ 种筹码，面值分别为 $a_1,a_2,\\ldots,a_m$ 澳元（均为正整数）**，每种一个，保证公平。\n3. 本赌场仅提供一种游戏：猜拳。游戏开始时，双方各下注相同数量（以 $1$ 澳元为单位）的筹码；若猜拳分出胜负，则胜者拿走所有下注。\n4. 根据上一条可知，**玩家一次游戏中赢得的筹码（正整数）不得超过自身所携带的筹码**。\n5. 公平游戏，严禁作弊，违者严惩。\n\nxhabc66 注册后，**连赢数局（可以是 $0$ 局，但没有输过，也没有平局过）**，最终带着 $n$ 澳元走出了赌场。\n\n出赌场后，xhabc66 突然好奇他是怎么赢到这么多钱的。然而，他不记得他每局下了多少注，不记得他一共玩了多少局，甚至不记得他开始时拿走的筹码是什么面值。\n\n**他想知道：他有多少种不同的赢钱方法。**\n\n**答案对 $10^9+7$ 取模。**\n\n> 两种赢钱方法在满足以下任何一个条件时，xhabc66 都会认为它们不同：\n>\n> - 他某一局的下注金额不同；\n> - 他玩的局数不同；\n> - 他开始时拿走的筹码的面值不同。\n\n### 形式化题意\n\n求有多少个数列 $\\{b_k\\}$ 满足：\n\n1. $\\forall i \\in [1,k],b_i \\in \\mathbb{N^*}$；\n2. $\\forall i \\in [2,k],b_i \\in [b_{i-1}+1,b_{i-1} \\times 2]$；\n3. $b_1 \\in\\{a_m\\}$；\n4. $b_k=n$。\n\n数列的长度 $k$ 可以是任何**正整数**。\n\n答案对 $10^9+7$ 取模。\n\n## Input\n\n两行。\n\n第一行，两个正整数，$n,m$。\n\n第二行，$m$ 个**从小到大排列**的正整数，$a_1 \\sim a_m$。\n\n## Output\n\n一行一个正整数，表示答案。\n\n[samples]\n\n## Background\n\n## 本题目背景仅供引出题意，无任何不良诱导。\n## 出题人特别提醒：请勿在赌博非法地区模仿题目中的行为\n\n这天，xhabc66 来到澳门旅游。一下飞机，他直奔赌场。\n\n可是，今天的赌场格外热闹，不知发生了什么。\n\nxhabc66 打开手机一看：啊，原来今天是 $12$ 月 $20$ 日！\n\n因此，赌场在做活动！一年一度！机不可失！\n\nxhabc66 径直走进了赌场。\n\n## Note\n\n样例 $1$ 解释：\n\n```plain\n1 2 3 4\n1 2 4\n2 3 4\n2 4\n3 4\n4\n```\n\n样例 $2$ 解释：\n\n```plain\n1 2 3 4 5\n1 2 3 5\n1 2 4 5\n```\n\n----------\n\n**本题采用捆绑测试。**\n\n| Subtask 编号 | $m \\le$ | $n \\le$ | 分值 |\n| :-: | :-: | :-: | :-: |\n| $0$ | $3$ | $3$ | $20$ |\n| $1$ | $10^5$ | $10^5$ | $40$ |\n| $2$ | $10^6$ | $10^8$ | $40$ |\n\n对于 $100\\%$ 的数据，$1 \\le m \\le 10^6$，$1 \\le a_1<a_2<\\ldots<a_m \\le n \\le 10^8$，$m \\le n$。\n\n> **提示：** 请注意本题不同寻常的内存限制！","is_translate":false,"language":"English"}],"meta":{"iden":"LGP10036","tags":["动态规划 DP","倍增","2024","洛谷原创","O2优化","动态规划优化","前缀和"],"sample_group":[["4 4\n1 2 3 4","6"],["5 1\n1","3"],["12345678 9\n1 2 3 45 67 89 123 456 789","998899106"]],"created_at":"2026-03-03 11:09:25"}}