算术表达式 - 题目

#444. 算术表达式

统计

题目描述

我们如下定义表达式：

一个在 $[0,M-1]$ 内且没有多余前导零的整数是一个表达式
若 $E$ 是一个表达式，则 $(E)$ 是一个表达式
若 $E_1,E_2$ 是一个表达式，则 $E_1+E_2$ 和 $E_1-E_2$ 都是表达式

现在给定 $N,M,P$，你需要求有多少个长度为 $N$ 的表达式满足它的值模 $M$ 等于 $P$

由于答案可能非常大，你只需要输出答案对 $10^9+7$ 取模后的值

输入格式

输入只有一行，包含三个整数 $N,M,P$。保证 $0 \leq M < P$。

输出格式

输出一行一个整数，表示答案。

样例数据

样例 1 输入

3 100 98

样例 1 输出

样例 2 输入

50 200 70

样例 2 输出

130371982

子任务

对于 $30\%$ 的数据，$N \leq 6$。

对于 $50\%$ 的数据，$N \leq 20, M \leq 50$。

另有 $20\%$ 的数据，$M = 2$。

对于 $100\%$ 的数据，$1 \leq N \leq 50, 1 \leq M \leq 200$。

About Issues

We understand that our problem archive is not perfect. If you find any issues with the problem, including the statement, scoring configuration, time/memory limits, test cases, etc.

You may use this form to submit an issue regarding the problem. A problem moderator will review your issue and proceed it properly.

STOP! Before you submit an issue, please READ the following guidelines:

This is not a place to publish a discussion, editorial, or requests to debug your code. Your issue will only be visible by you and problem moderators. Other users will not be able to view or reply your issues.
Do not submit duplicated issues. If you have already submitted one, please wait for an moderator to review it. Submitting multiple issues will not speed up the review process and might cause your account to be banned.
Issues must be filed in English or Chinese only.
Be sure your issue is related to this problem. If you need to submit an issue regarding another problem, contest, category, etc., you should submit it to the corresponding page.

Active Issues 0

No issues in this category.

Closed/Resolved Issues 0