Background
The DSA (Digital Signature Algorithm) is a publickey cryptographic algorithm for creating digital signatures. The signature is created secretly but can be verified publicly. This means that only one subject can create a signature, but anyone can verify its correctness. The algorithm is based on the computational complexity of taking logarithms in finite fields.
The first phase of key generation is a choice of algorithm parameters which may be shared between different users of the system.
 Choose an approved cryptographic hash function H (for example SHA2). The hash output may be truncated to the size of a key pair.
 Decide on a key length L and N. This is the primary measure of the cryptographic strength of the key. The minimal recommended values for L and N are 1024 and 160.
 Choose an Nbit prime q. N must be less than or equal to the hash output length.
 Choose an Lbit prime modulus p such that p − 1 is a multiple of q.
 Choose g, a number whose multiplicative order modulo p is q. This may be done by setting g = h ^{(p − 1) / q} mod p for some arbitrary h (1 < h < p − 1), and trying again with a different h if the result comes out as 1. Most choices of h will lead to a usable g; commonly h = 2 is used.
Given a set of parameters, the second phase computes private and public keys for a single user:
 Choose x by some random method, where 0 < x < q.
 Calculate y = g ^{x} mod p.
 Public key is (p, q, g, y). Private key is x.
Let m be the message and H(m) the hash value of that message.
 Generate a random permessage value k where 0 < k < q.
 Calculate r = (g^{k} mod p) mod q.
 In the unlikely case that r = 0, start again with a different random k.
 Calculate s = k^{−1}(H(m) + x r) mod q.
 In the unlikely case that s = 0, start again with a different random k.
 The signature is (r, s).
 Reject the signature if 0 < r < q or 0 < s < q is not satisfied.
 Calculate w = s^{−1} mod q.
 Calculate u_{1} = H(m) w mod q.
 Calculate u_{2} = r w mod q.
 Calculate v = ((g^{u1} y^{u2}) mod p) mod q.
 The signature is valid if v = r.
Problem
Given the public key (q, p, g, y) and the hash value of the message H(m) you are to create a valid signature (r, s).
Input
The single line of input contains integers N, L, q, p, g, y, H(m). The following limitations are applied:
 3 ≤ N ≤ 36;
 6 ≤ L ≤ 60, L ≥ N + 3;
 q is an exactly Nbit integer;
 p is an exactly Lbit integer;
 1 < g < p;
 0 ≤ y < p;
 H(m) is an Nbit integer.
The public key is guaranteed to be generated as described above.
Output
The single line of output should contain the integers r and s separated with space. The pair (r, s) must be valid DSA signature for the public key (q, p, g, y). There are multiple valid signatures, you may output any of them.
Sample
input  output 

3 6 5 41 10 16 2
 3 3

Problem Author: Prepared by Vladimir Yakovlev. Text by Wikipedia, the free encyclopedia.